재귀(Recursion) : 주어진 문제를 그보다 작은 문제로 환원하는 것.
재귀호출(Recursive Call) : 프로그램을 실행하기 위해 자기 자신을 호출(Self call)하는 것.
문제 크기(Problem Size)는 데이터 양(Data Size)을 말한다. 크기 100의 문제를 크기 99의 문제로, 이를 다시 크기 98의 문제로 환원해서 결국에는 곧바로 해결 가능한 크기 1의 문제로 만들 때, 이처럼 큰 문제를 보다 작은 문제로 환원하여 이를 해결함으로써 큰 문제의 해결에 이르는 접근 방식을 분할 정복(Divide and Conquer) 전략이라 부른다. (수학적 귀납법-Mathematical induction과 순서를 반대로 적용한다고 보면 된다.)
재귀호출 함수가 자기 자신을 호출하는 이유는 작은 문제의 스타일이 원래의 큰 문제 스타일과 동일하기 때문이다. 문제 크기만 다를 뿐, 완전히 동일한 문제라는 것이 특징이다.
문제의 크기가 직접 해결할 수 있을 정도로 작아졌을 때는 베이스 케이스(Base Case) 또는 디제너릿 케이스(Degenerate Case)라고 부르며 재귀호출은 결국 문제 크기를 계속 줄여 나가, 직접 정복 가능한 베이스 케이스로 환원함으로써 문제를 해결한다. 모든 재귀호출은 최종적으로는 이처럼 직접 정복할 수 있는 베이스 케이스로 환원될 수 있어야 한다.
이진 탐색
사전을 찾을 때 가장 단순한 탐색 방법은 첫 페이지부터 시작해서 원하는 단어가 나올 때까지 뒤지는 것이다. 이를 순차탐색(Sequential Search) 또는 선형탐색(Linear Search)라고 부르며 이 방법에서 얼마나 빨리 찾을 수 있는지는 순전히 운에 달려 있다. 얼마나 빨리 찾는지를 탐색의 효율(Efficiency)이라고 정의할 때, 효율이 이처럼 운에 달린 방법에서는 사실 사전 자체가 정렬되어 있을 필요조차 없다. 어떤 단어를 찾을지 모르기 때문이다.
정렬된 사전을 전제로 할 때, 이보다 나은 탐색 방법이 이진탐색(Binary Search)이다. 유사코드(Pseudo-Code)로 이진탐색 방법을 나타내면 다음과 같다.
BinarySearch (SearchRange) // 괄호 안은 탐색 범위
if (One Page) // 베이스 케이스
Scan Until Found;
else {
Unfold the Middle Page; // 가운데 펼침
Determine Which Half; // 전반부, 후반부 판단
if First Half
BinarySearch (First Half); // 전반부 재귀호출
else BinarySearch (Second Half); // 후반부 재귀호출
}
사전의 한 가운데를 펼치면 찾는 단어가 펼친 페이지보다 앞에 있을지 뒤에 있을지를 판단할 수 있다. 만약 앞에 있다면 다시 전반부의 한 가운데를 펼쳐서 찾는 단어가 앞에 있을지 뒤에 있을지를 판단한다. 이러한 과정을 반복하면 결국 포위망은 한 페이지로 줄어들게 되고 그 페이지를 위에서부터 스캔하면 해당 단어를 찾을 수 있게 된다. 단, 이러한 이진 탐색을 적용하려면 원래의 데이터가 정렬되어 있어야 한다.
문제의 크기 : N -> N/2 -> N/4 -> ... -> 1
여기서 함수명이 BinarySearch인 위 유사코드 내부에서 다시 BinarySearch 를 부르는 것이 바로 재귀호출이다. 같은 함수를 부른다고 해서 프로그램 실행 도중 메인 메모리에 동일한 함수가 하나 더 생기는 것은 아니다. 메인 메모리에는 여전히 단 하나의 함수만 있으며, 단지 Goto 명령에 의해 다시 함수의 첫 줄이 실행된다고 간주하면 된다.
재귀호출에서 반드시 검증해야 하는 것이 문제의 크기다. 호출할 때마다 문제의 크기는 작아져야 하고, 그것이 최종적으로는 베이스 케이스와 일치해야 한다. 만약 호출할 때마다 문제의 크기가 커지거나 문제 크기는 줄어들지만 베이스 케이스로 정의한 조건과 일치하지 않고 이를 피해 간다면 결국에는 프로그램을 종료할 수 없게 되버린다. 계속 자기 자신을 부르는 재귀호출에서 빠져나오는 유일한 방법은 베이스 케이스에 도달하는 것뿐이다.
팩토리얼
자연수 n에 대해서 n! (n 팩토리얼)은 다음과 같이 정의된다.
n! = n x (n-1) x (n-2) ... x 1 (단, 1! = 0! = 1)
크기 n의 문제를 재귀적으로 생각하면 그보다 작은 문제로 환원해야 한다. 예를 들어, 1만큼 작은 문제라면 (n-1)!이 되고 둘 사이의 관계는 n! = n * (n-1)! 이 된다. (n-1)! 은 다시 (n-2)!를 구하고 거기다 (n-1)을 곱하면 해결된다. 그렇다면 5!이 4!을 구하는 문제로, 이것이 다시 3!을 구하는 문제로 바뀐다. 결국 이 문제는 재귀적으로 해결할 수 있는 문제다.
베이스 케이스는 1!로 하면 된다. 1! = 1로 정의되었기 때문이다. 그러나 여기서 반드시 고려해야 할 것은 항상 베이스 케이스에 도달하는지에 대한 문제다. 숫자 5, 20, 400 모두 1씩 줄여 가면 반드시 1!이라는 베이스 케이스를 만난다. 음수와 같은 입력은 n이 자연수여야 한다는 정의에 어긋나므로 가정하지 않는다.
int Factorial (int n) {
if (n == 1)
return 1;
else
return (n * Factorial(n-1));
}
호출 함수인 Factorial(n)이 Factorial(n-1)을 부르면 (n-1)이 파라미터 n에 값 호출로 복사되어 들어가면서 피호출 함수(Called Function)가 실행된다. 호출 함수로서는 피호출 함수의 리턴 값인 (n-1)!이 자신에게 돌아와야만, 그때 가서 거기에 n을 곱해 자신을 부른 함수에게 자신의 리턴 값을 돌려줄 수 있다. 다음 4!을 구하는 과정을 그림으로 보며 참고하자. (F -> Factorial 함수)
모든 피호출 함수는 실행이 끝나면 바로 이전에 자신을 호출한 함수의 다음 명령어로 되돌아간다. 피호출 함수인 (1!)의 수행이 끝나면 호출 함수로서는 2 * (1!)을 계산하는 것이 바로 다음 실행할 명령어가 되는 것이다.
문자열 뒤집기
길이 n인 문자열을 뒤에서 앞으로 거꾸로 써나가는 문제를 생각해보자. 예를 들어, 길이 4인 문자열 "Good"를 거꾸로 쓰면 "dooG"가 된다. 이 문제를 재귀적으로 풀려면 길이 n의 문제를 길이 (n-1)의 문제로 환원하면 된다. 또, 주어진 문자열의 길이를 하나 줄이려면 당연히 문자 하나를 떼어내면 된다. 어떤 문자를 떼어내느냐에 따라 문제에 대한 해결책은 두 가지로 나뉜다.
1. 마지막 문자 제거
문자열을 뒤집으려고 마지막 문자를 떼어낸다고 생각하면, 일단 그 문자를 먼저 쓰고 떼어내면 된다.
void Reverse (char S[], int Size) {
if (Size == 0)
return; // 호출 함수로 되돌아감
else {
printf("%c", S[Size-1]); // 마지막 문자를 쓰기
Reverse(S, Size-1); // 재귀호출
}
}
베이스 케이스에 해당하는 길이가 0인 문자열이 들어오면 아무 일도 하지 않고 호출 함수로 되돌려진다. 베이스 케이스가 아니라면 마지막 문자를 찍고 재귀호출을 가한다. 이때 파라미터 값으로 (Size-1)을 넘김으로서 배열의 길이를 하나 줄이는 효과를 얻는다. 실제 배열의 모든 내용은 그대로 있으나 길이 변수를 줄임으로서 배열의 끝을 한 칸 앞쪽으로 당긴 것이다. 재귀호출 이전에 실제로 화면에 찍는 작업을 수행한 후 재귀호출을 함으로써 찍고 들어가고, 찍고 들어가고를 반복하게 된다. 베이스 케이스 실행이 끝나고 호출 함수로 되돌아오면 그 이후의 명령어가 없으므로 아무런 실행 없이 자신을 호출한 함수로 되돌려진다. 재귀호출에서 되돌아가는 과정에서는 아무런 작업도 하지 않는 것이다.
2. 첫 문자 제거
첫 글자를 떼어내는 효과를 가하려면 배열의 첫 문자를 가리키는 인덱스를 증가시키면 된다. 현재 고려되고 있는 문자의 처음을 First로, 마지막을 Last라는 인덱스로 표시하고 메인 함수에서 Reverse(S, 0, 3)을 호출한다고 가정하자. 문자열 S로는 "Good"을 넘겨주었다.
void Reverse(char S[], int First, int Last) {
if (First > Last)
return;
else {
Reverse(S, First+1, Last);
printf("%c", S[First]);
}
}
처음 First = 0, Last = 3인 상태에서 Reverse(S, 1, 3)의 바로 다음 명령어는 S[First]를 찍는 것이다. 즉 현재 상태에서의 S[First]인 S[0]을 찍는 명령을 Reverse(S, 1, 3)의 수행이 끝날 때까지 유보하겠다는 것이다. 그런데 Reverse(S, 1, 3) 역시 나중에 S[1]을 찍는 것을 전제로 일단 Reverse(S, 2, 3)을 호출한다. 같은 방식으로 이러한 호출이 반복된다.
이 코드에서 실제 작업은 빠져 나오는 과정에서 이루어진다. 즉, 재귀호출에 의해 깊숙이 파고 들어가는 과정에서는 아무런 일도 일어나지 않는다. 그저 호출만 계속 일어날 뿐이다. First = 3, Last = 3인 상태에서 Reverse(S, 4, 3)을 부르면 베이스 케이스로 리턴되어 돌아온다. 따라서 호출 함수에서 다음에 수행해야 할 명령어는 printf 문으로 그 상황에서의 S[First]인 S[3]이 찍히게 된다. 이를 그림으로 표현하면 다음과 같다. (R -> Reverse 함수, F -> First, L -> Last)
경우에 따라서는 이처럼 재귀호출에서 빠져나오면서 실제 작업이 이루어지는 때도 있다.
K번째 작은 수 찾기
정렬되지 않은 숫자들 중 K번째 작은 수를 찾아보자. 10, 7, 2, 8, 3, 1, 9, 6이라는 숫자 중에서 세 번째 작은 수는 3이 된다. 이 문제를 재귀적으로 생각했을 때 숫자 8개를 반으로 갈라서 10, 7, 2, 8과 3, 1, 9, 6으로 나누어 생각한다면 왼쪽 중 세 번째 작은 수는 8, 오른쪽에서는 6으로 나오게 된다. 큰 문제를 잘라서 작은 문제로 환원했을 때, 작은 문제의 해결책이 큰 문제의 해결책으로 이어지는 것이 재귀다. 그러나 이 경우는 작은 문제의 해결책인 8, 6과 큰 문제의 해결책인 3과 연관지어지지 않는다. 그렇다면 이 문제의 재귀적인 해결책은 뭘까?
파티션(Partition)이란 어떤 수를 중심으로 나머지 수를 두 그룹으로 나누는 작업을 말한다. 즉, 기준이 되는 수를 중심으로 그보다 작은 것들은 왼쪽, 큰 것들은 오른쪽에 위치하도록 나누는 것이다. 이때 기준이 되는 숫자를 피벗(Pivot, 중심점)이라고 한다. 위 문제를 해결하기 위해 파티션을 가해보자. 파티션 방법은 다음과 같다.
- 임의로 피벗을 설정한다. (예를 들어 마지막 숫자)
- 오른쪽에서 왼쪽으로 내려가는 다운 포인터(Down Pointer)와, 반대로 왼쪽에서 오른쪽으로 올라가는 업 포인터(Up Pointer)를 설정한다.
- 두 포인터를 움직이되, 다운 포인터는 피벗보다 작거나 같은 것, 업 포인터는 피벗보다 크거나 같은 것에서 멈춘다.
- 다운 포인터와 업 포인터 위치의 숫자를 서로 교환(Swapping)한다.
- 위 3, 4의 작업을 반복하되 두 포인터가 일치하거나 교차(Cross Over)하면 정지한다.
- 업 포인터 위치에 있는 숫자와 피벗 숫자를 교환한다.
결과 모습은 피벗을 중심으로 파티션된 모습이다. 즉 피벗보다 작은 수는 피벗의 왼쪽에, 큰 수는 오른쪽에 위치한다. 왼쪽 숫자들끼리 또는 오른쪽 숫자들끼리는 정렬되지 않았다는 점에서 조금 느슨한 의미의 정렬이라고 말할 수 있다.
만약 우리가 찾는 것이 네 번째 작은 수였다면 그것은 당연히 현재 피벗인 6이 된다. 왼쪽끼리, 오른쪽끼리 모두 정렬을 완료하더라도 피벗인 6의 위치는 변하지 않기 때문이다. 우리가 찾는 세 번째 작은 숫자는 피벗의 왼쪽에 있다. 따라서 이번에는 피벗 왼쪽의 숫자들만에 대해 파티션을 가하고 결과적인 피벗 위치에 주목하면 된다.
1, 3, 2에 대해 마지막 요소인 2를 기준으로 파티션을 하면 시작하자마자 두 포인터가 교차하고 따라서 피벗은 두 번째 작은 수가 된다. 우리가 찾는 것은 세 번째 작은 수므로 이번에는 피벗의 우측에 있는 3을 대상으로 파티션을 해보자. 사실 이 경우는 재귀호출로 말하면 베이스 케이스에 해당한다. 즉, 숫자 하나는 그 자체가 이미 파티션된 결과다. 따라서 이 문제를 풀기 위해 순차적으로 파티션을 가한 결과, 피벗의 위치는 네 번째, 두 번째, 세 번째에 나타나고, 따라서 우리가 찾고자 하는 숫자는 세 번째에 나타난 숫자 3이 된다.
결과적으로 K번째로 작은 숫자를 찾는 문제는 재귀적으로 해결할 수 있다. 임의로 피벗을 선정하여 파티션을 가하고 결과적인 피벗 위치가 K번째 인지 확인한다. 만약 그렇다면 바로 그 피벗 숫자가 우리가 찾는 K번째 작은 수가 된다. 만약, K가 피벗 위치보다 크면 현재 피벗의 오른쪽에 대해서, 그렇지 않으면 왼쪽에 대해서 같은 방법으로 재귀호출에 의해 파티션을 계속한다.
문제의 크기가 얼마로 줄어드느냐는 파티션 결과, 피벗의 위치가 어디냐에 따라서 좌우된다.
K번째 작은 수가 있을 것으로 생각되는 부분에 한해서만 파티션을 가했지 나머지 부분에 대해서는 파티션을 가하지 않았기에 정렬과는 무관하다. 만약 우리가 숫자 하나만 남는 베이스 케이스를 만날 때까지 계속해서 왼쪽, 오른쪽 모두에 파티션을 반복했다면 모든 데이터가 정렬될 것이며, 이를 퀵 정렬(Quick Sort)이라고 한다.
피보나치 수열
0, 1, 1, 2, 3, 5, 8, 13, 21, ...로 진행하는 수열을 피보나치 수열(Fibonacci Sequence)이라 한다. F(0) = 1, F(1) = 1로 잡으면 F(n)은 다음과 같은 일반식으로 표현될 수 있다.
F(n) = F(n-1) + F(n-2) (단, F(0) = F(1) = 1)
재귀적인 연관성을 나타내는 이러한 식을 재귀식, 또는 점화식 (Recurrence Relation)이라 한다.
피보나치 관계식은 큰 문제 하나를 그보다 작은 문제 두 개로 나누고, 각각의 해결책을 합해서 큰 문제의 해결책에 이른다. 재귀 호출 하나가 다른 여러 재귀호출의 조합 형태로 나타날 수도 있다. 이 관계식을 이용하여 n번째 피보나치 수열을 구하는 함수는 다음과 같다.
int Fibonacci (int n) {
if (n < 2)
return 1;
else return (Fibonacci(n-1) + Fibonacci(n-2));
}
n = 5일 때 Fibonacci(5)에 의해 재귀호출되는 함수는 다음과 같다.
여기서 F(3) 호출은 두 번, F(2)는 세 번, F(1)은 무려 다섯 번이 반복되는데, 한 번 계산해 놓은 것을 저장하고 재사용하는 방법에 비해 동일한 계산을 반복하는 것은 프로그램의 효율성(Efficiency)이 그만큼 떨어짐을 의미한다.
재귀 함수의 작성
- 주어진 문제를 더 작은 문제로 표시할 수 있는지 시도하고, 만약 그렇다면 문제의 크기에 해당하는 파라미터 N을 알아낸다. 문제 크기를 하나씩 줄이는 방법, 반으로 줄이는 방법, 다른 여러 개의 작은 문제의 조합으로 표시하는 방법 등을 시도한다.
- N이 작아져서 문제를 직접 풀 수 있는 것이 어떤 경우인지 베이스 케이스를 알아낸다. N이 충분히 작아져서 문제를 직접 해결할 수만 있다면 베이스 케이스를 그 이하로 책정할 필요는 없다.
- 일반적인 N이 주어졌을 때, 그 N이 줄어들어 반드시 베이스 케이스를 만나게 되는지 확인한다. 이는 N이 양수인지 음수인지, 짝수인지 홀수인지, 또는 부동소수인지 정수인지 각각의 경우에 대해 모두 검증되어야 한다.
- 베이스 케이스와 베이스 케이스가 아닌 경우를 나누어서 코드를 작성한다.
재귀호출의 효율성
재귀호출은 효율 면에서 크게 불리하다. 반복적인 재귀호출에 따른 활성화 레코드의 관리에는 시간적, 공간적 자원을 필요로 한다. 시간(CPU Time)적으로는 활성화 레코드를 쓰기 위한 시간, 또 나중에 되돌아오면서 이전 상태를 복원하기 위해 쓰인 내용을 다시 읽는 시간을 필요로 한다. 공간(Memory Space)적으로는 호출할 때마다 활성화 레코드를 쌓아나가기 위해 스택 메모리 공간을 필요로 한다. (활성화 레코드 만드는 횟수 가능한 적게 해야 함)
재귀호출이 내재하는 비효율성을 감안할 때, 재귀호출 없이 해결될 수 있으면 당연히 그 방법을 사용해야 한다. 대부분의 경우 재귀호출은 반복문으로 대체할 수 있다. 반복문을 사용할 시 빠르고 메모리도 적게 사용하므로 가능하다면 대치하는 것이 유리하다. 다음은 반복문에 의한 팩토리얼, 문자열 뒤집기, 피보나치 프로그램을 순차적으로 쓴 것이다.
int Factorial(int n) { // 팩토리얼
int product = 1; // 곱셈의 결과 값을 초기화
for (int i = 1; i <= n; i++) // 1부터 n까지
product *= i; // 계속 곱해서 저장
return product; // 결과 리턴
}
void Reverse(char S[], int Size) { // 문자열 뒤집기
while (Size > 0) { // 한 글자라도 남아 있을 때까지
printf("%c", S[Size-1]); // 일단 마지막 문자를 찍고
--Size; // 문자열 마지막을 한 칸 앞으로
}
}
int Fibonacci (int n) { // 피보나치 수열
int F[Max]; // 배열 크기 n보다 크게 잡음
F[0] = 1; F[1] = 1; // 수열의 처음 두 숫자 초기화
for (int i = 2; i <= n; i++) // F[2]부터 n까지
F[i] = F[i-2] + F[i-1]; // 앞에서 뒤로 채워나감
return F[n]; // 배열의 마지막 요소 돌려줌
}
위 예의 for나 while 루프처럼 쉽게 반복문으로 치환할 수 있는 경우도 있지만 달리 치환하기가 매우 까다로운 경우도 존재한다. (이진탐색의 경우 재귀호출이 더 유리) 이러한 점을 감안하여 프로그램의 간명함이 중시될 때에는 재귀호출을 사용하는 것이 좋으나, 간명함보다 효율이 중요시 될 때에는 어렵더라도 반복문으로 치환해야 한다.
꼬리재귀
꼬리재귀(Tail Recursion)란 재귀호출 명령이 함수의 제일 마지막에 오는 것이다. 꼬리재귀는 호출의 리턴 값이 수식 표현(Expression)의 일부여서는 안 된다. 꼬리재귀의 특성은 재귀호출에서 되돌아오면 할 일이 전혀 없는 것이다. 대부분의 컴파일러는 꼬리재귀의 이러한 특성을 이용해 재귀호출이 일어날 때 새로운 활성화 레코드를 쌓아 올리는 대신 이전의 활성화 레코드에 새로운 활성화 레코드를 덧씌워(Overwriting) 버린다. 즉, 이전 활성화 레코드가 사용하던 공간을 새로운 활성화 레코드로 대치시킴으로써 메모리의 공간적 효율을 기한다. 나중에 되돌아오면서 할 일이 없으므로 그 이전 상황을 복원할 필요가 없기 때문이다.
팩토리얼 함수에 꼬리재귀를 사용하면 다음과 같다.
int Factorial(int n, int a) {
if (n == 0)
return a; // a에 결과 값이 축적됨
else
return Factorial(n-1, n*a); // 꼬리재귀
}
4!을 구하려면 Factorial(4, 1)을 실행하면 된다. 이렇게 되면 호출은 Factorial(4, 1) -> Factorial(3, 4) -> Factorial(2, 12) -> Factorial(1, 24) -> 24로 된다. 즉 리턴 될 값을 a에 쌓아가면서 재귀호출을 계속하되, 베이스 케이스에 a를 리턴해버리면 나중에 호출 함수로 되돌아가면서 할 일이 없어져 버린다. 끝나고 돌아왔을 때 할 일이 없다는 것은 굳이 공간을 저장할 필요가 없다는 뜻이므로 용량이 절약되고 Stack Overflow가 발생하지 않는다.
'알고리즘' 카테고리의 다른 글
| [백준] 경쟁적 전염 (0) | 2025.02.24 |
|---|---|
| [백준] 연구소 (0) | 2025.02.24 |
| [백준] 특정 거리의 도시 찾기 (0) | 2025.02.24 |
| [프로그래머스] 외벽 점검 (0) | 2025.02.22 |
| [LeetCode] Valid Parentheses (0) | 2024.03.29 |