재귀

재귀적 정의

팩토리얼

자연수 $n$의 팩토리얼은 1부터 $n$까지의 자연수의 곱이다. 곧 $n! = 1 \cdot 2 \cdots n$이고, $0! = 1$로 약속한다. 이 식의 말줄임표는 반복문을 숨기고 있으며, 그것을 쓰는 법은 반복문 수업에서 배웠다. 그런데 같은 정의는 반복문을 전혀 언급하지 않는 다른 형태도 허용한다. $n$의 팩토리얼은 $n$에 $n - 1$의 팩토리얼을 곱한 것이고, 0의 팩토리얼은 1이다.

이것이 재귀적 정의이다. $n$의 팩토리얼을 더 작은 수의 팩토리얼로 정의한다. 순환 논법이 아니다. 두 번째 규칙을 한 번 쓸 때마다 계단을 한 칸 내려가고, 그 계단은 첫 번째 규칙에서 끝나기 때문이다: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. 두 규칙에는 이름이 있다. 첫 번째는 기저 사례로, 다른 무엇에도 기대지 않고 결과를 준다. 두 번째는 재귀 사례로, 문제를 같은 문제의 더 작은 사례로 환원한다.

C++에서는 함수가 자기 자신을 호출할 수 있고, 덕분에 정의를 거의 한 단어씩 그대로 옮길 수 있다.

#include <print>​// n의 팩토리얼.// 사전 조건: 0 <= n <= 12 (이 상한의 근거는 뒤에서 밝힌다).// 사후 조건: n! = 1 · 2 · ... · n을 반환한다. 단, 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // 기저 사례    }    return n * factorial(n - 1);    // 재귀 사례}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

계약은 장식이 아니다. $n = -1$일 때 재귀 사례는 $-2$로, 이어서 $-3$으로 호출하며 결코 0에 이르지 못한다. 또 $13!$의 값은 int 타입에 들어가지 않는다. 많은 입문서는 이 팩토리얼을 기저 사례 if (n == 0 || n == 1)로 쓰는데, 이는 군더더기이지만 해는 없다. 그러나 음수에 대해서도 결과의 크기에 대해서도 아무 말이 없어서, 그 코드는 $n < 0$일 때 멈추지 않고 $13!$부터는 의미 없는 결과를 낸다. 두 결함은 각각 해당하는 절에서 살펴본다.

기저 사례와 재귀 사례

모든 재귀 함수에는 직접 풀리는 기저 사례가 하나 이상 있고, 어떤 정확한 의미에서 더 작은 인자로 같은 함수를 호출하여 그 반환값을 조합하는 재귀 사례가 하나 이상 있다.

거듭제곱 $x^n$의 경우, 지수 $n$은 자연수이며 $x^0 = 1$과 $x^n = x \cdot x^{n - 1}$로 정의된다. 여기서 크기는 지수이다. 자연수 $n$의 자릿수 합(2026의 경우 $2 + 0 + 2 + 6 = 10$)은 이렇게 정의된다. $n < 10$이면 합은 $n$이다. 자리가 하나뿐이기 때문이다. 그렇지 않으면 $\lfloor n / 10 \rfloor$의 자릿수 합(이것은 $n$에서 마지막 자리를 뺀 수이다)에 그 마지막 자리 $n \bmod 10$을 더한 것이다. 여기서 크기는 자릿수이다.

#include <print>​// x의 n제곱.// 사전 조건: n >= 0.// 사후 조건: x^n을 반환한다. 단, x^0 = 1.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// n의 십진 자릿수의 합.// 사전 조건: n >= 0.// 사후 조건: n의 자릿수의 합을 반환한다.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("2026의 자릿수 합: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.3752026의 자릿수 합: 10

그러므로 재귀 함수를 쓴다는 것은 두 질문에 답하는 일이다. 어떤 경우가 도움 없이 풀리는가, 그리고 어떤 경우의 해를 더 작은 경우의 해로부터 어떻게 얻는가. 두 답이 모두 옳으면 함수도 옳으며, 그것을 이어지는 절에서 증명한다.