다음은 재귀 알고리즘의 바탕이 되는 기본 개념입니다.
어떤 문제를 해결하기 위해, 문제의 범위보다 약간 좁은 하위 문제를 해결합니다. 그다음에 하위 문제에 대한 해답을 이용하여 원래 문제를 해결합니다.
이전에 n! n! 을 계산할 때 n! n! 을 바로 계산하는 대신 이보다 더 작은 (n1)! (n-1)! (범위가 더 좁은 하위 문제) 을 계산하였고, 이에 대한 해답을 이용하여 n! n! 의 값을 계산하였습니다.
재귀 알고리즘이 실제로 작동하려면 범위가 더 좁은 하위 문제가 base case에 도달하여 재귀함수가 끝날 수 있어야 합니다. n! n! 을 계산할 때, 하위 문제는 점점 작아져 0!0!에 도달합니다. 이런 base case 가 반드시 있어야 합니다.
예를 들어, 음수에 대한 계승을 재귀를 통해 계산한다고 생각해봅시다. (1)! (-1)! 을 계산하려면 먼저 (2)! (-2)! 를 계산하여 이 값을 minus, 1로 곱해야 합니다. 그런데 (2)! (-2)! 을 계산하려면 먼저 (3)! (-3)! 를 계산하고 여기에 minus, 2를 곱해야 합니다. (3)! (-3)! 을 계산하려고 해도 마찬가지 결과를 얻게 됩니다. 물론 값은 점점 작아지겠지만, base case 인 0!0! 과는 점점 거리가 멀어집니다. 이렇게는 절대로 답을 구할 수 없습니다.
만약에 n의 값이 음수가 아니라고 해도 하위 문제의 값을 점점 작아지도록 만들지 않으면 같은 문제를 맞닥뜨리게 됩니다. 예를 하나 들어봅시다. n!=n(n1)! n! = n \cdot (n-1)! 의 양변을 n 으로 나눠서 n!/n=(n1)! n! / n = (n-1)! 로 바꿔봅시다. 이제 새로운 변수 mn, plus, 1과 같다고 놓습니다. 이 공식은 모든 양수에 대해 성립하므로 mn으로 치환하여 m!/m=(m1)! m! / m = (m-1)! 으로 바꿀 수 있습니다. m, equals, n, plus, 1 이므로 다시 (n+1)!/(n+1)=(n+11)! (n+1)! / (n+1) = (n+1-1)! 이렇게 나타낼 수 있습니다. 변의 위치를 바꾸고 n, plus, 1, minus, 1, equals, n이므로, n!=(n+1)!/(n+1) n! = (n+1)! / (n+1) 으로 바꿀 수 있습니다. 위 공식을 이용하면 (n+1)! (n+1)! 을 먼저 풀고 그 값을 n, plus, 1로 나누어 마침내 n! n! 을 풀 수 있습니다. 그러나 (n+1)! (n+1)! 을 풀려면 먼저 (n+2)! (n+2)! (n+3)! (n+3)! 을 먼저 풀어야 합니다. 결국 base case 인 0에 도달할 수 없습니다. 그 이유는 하위 재귀 문제 각각이 해당 값보다 더 작은 수가 아닌 더 수의 계산을 요구하기 때문입니다. 만일 n이 양수라면 0 인 base case에 절대 도달할 수 없습니다.
재귀의 반복 개념은 다음과 같이 두 개의 간단한 규칙으로 간추릴 수 있습니다.
  1. 재귀의 호출은 같은 문제 내에서 더 범위가 작은 값, 즉, 하위 문제에 대해 이루어져야 한다.
  2. 재귀함수 호출은 더 이상 반복되지 않는 base case에 도달해야 한다.
러시아 인형 이야기로 돌아가 봅시다. 러시아 인형은 어떤 알고리즘에 딱 들어맞는다고 할 수는 없지만, 인형 각각에는 안에 더 작은 인형이 들어있습니다 (재귀함수). 인형은 점점 작아지다가 결국 가장 작은 인형만 남습니다 (base case).

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