재귀 알고리즘의 속성

다음은 재귀 알고리즘의 바탕이 되는 기본 개념입니다.

이전에 $n!$‍을 계산할 때 $n!$‍을 바로 계산하는 대신 이보다 더 작은 $(n-1)!$‍ (범위가 더 좁은 하위 문제) 을 계산하였고, 이에 대한 해답을 이용하여 $n!$‍의 값을 계산하였습니다.

재귀 알고리즘이 실제로 작동하려면 범위가 더 좁은 하위 문제가 base case에 도달하여 재귀함수가 끝날 수 있어야 합니다. $n!$‍을 계산할 때, 하위 문제는 점점 작아져 $0!$‍에 도달합니다. 이런 base case 가 반드시 있어야 합니다.

예를 들어, 음수에 대한 계승을 재귀를 통해 계산한다고 생각해봅시다. $(-1)!$‍을 계산하려면 먼저 $(-2)!$‍를 계산하여 이 값을 $-1$‍로 곱해야 합니다. 그런데 $(-2)!$‍을 계산하려면 먼저 $(-3)!$‍를 계산하고 여기에 $-2$‍를 곱해야 합니다. $(-3)!$‍을 계산하려고 해도 마찬가지 결과를 얻게 됩니다. 물론 값은 점점 작아지겠지만, base case 인 $0!$‍ 과는 점점 거리가 멀어집니다. 이렇게는 절대로 답을 구할 수 없습니다.

만약에 $n$‍의 값이 음수가 아니라고 해도 하위 문제의 값을 점점 작아지도록 만들지 않으면 같은 문제를 맞닥뜨리게 됩니다. 예를 하나 들어봅시다. $n!=n\cdot (n-1)!$‍ 의 양변을 n 으로 나눠서 $n!/n=(n-1)!$‍ 로 바꿔봅시다. 이제 새로운 변수 $m$‍을 $n+1$‍과 같다고 놓습니다. 이 공식은 모든 양수에 대해 성립하므로 $m$‍을 $n$‍으로 치환하여 $m!/m=(m-1)!$‍으로 바꿀 수 있습니다. $m=n+1$‍ 이므로 다시 $(n+1)!/(n+1)=(n+1-1)!$‍ 이렇게 나타낼 수 있습니다. 변의 위치를 바꾸고 $n+1-1=n$‍이므로, $n!=(n+1)!/(n+1)$‍으로 바꿀 수 있습니다. 위 공식을 이용하면 $(n+1)!$‍을 먼저 풀고 그 값을 $n+1$‍로 나누어 마침내 $n!$‍을 풀 수 있습니다. 그러나 $(n+1)!$‍을 풀려면 먼저 $(n+2)!$‍과 $(n+3)!$‍을 먼저 풀어야 합니다. 결국 base case 인 0에 도달할 수 없습니다. 그 이유는 하위 재귀 문제 각각이 해당 값보다 더 작은 수가 아닌 더 큰 수의 계산을 요구하기 때문입니다. 만일 $n$‍이 양수라면 0 인 base case에 절대 도달할 수 없습니다.

재귀의 반복 개념은 다음과 같이 두 개의 간단한 규칙으로 간추릴 수 있습니다.

러시아 인형 이야기로 돌아가 봅시다. 러시아 인형은 어떤 알고리즘에 딱 들어맞는다고 할 수는 없지만, 인형 각각에는 안에 더 작은 인형이 들어있습니다 (재귀함수). 인형은 점점 작아지다가 결국 가장 작은 인형만 남습니다 (base case).

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.