再帰

再帰的定義

階乗

自然数 $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

したがって、再帰関数を書くとは二つの問いに答えることである。どの場合が助けなしに解けるか、そして、ある場合の解をより小さい場合の解からどう得るか。両方の答えが正しければ関数も正しく、それを以下の節で証明する。