【再帰的プログラム】再帰・帰納の違いを解説【階乗0!が1の理由】

こんにちは。iQeda [@iQeeeda] です。

階乗 0! が 1 になる理由は「そういうルールだからあまり気にするな」と言ったことがあります。

そして前回の復習ですが、
n を表現するために n - 1 という表現を使うことを「再帰」と言いました。

無数の証明ができる「数学的帰納法」では「基底」と「帰納」を行います。

再帰 (recursion) と帰納 (induction) の本質は同じです。
どちらも「大きな問題を、同じ形をした小さな問題に帰着させる」ことをしています。

数学的帰納法の証明を C 言語でプログラムにすると以下のようになります。
k = k + 1; していることから「小さなものから、段々と大きいもの」に進むことが分かります。

// p(0) から P(n) まで証明を行う
void prove(int n) {
    int k;

    k = 0;

    printf("基底より、P(%d)が成り立ちます。\n", k);

    while (k < n) {
        printf("帰納より「P(%d)が成り立つならばP(%d)も成り立つ」といえます。\n", k, k + 1);
        printf("したがって「P(%d)が成り立つ」といえます。\n", k + 1);
        k = k + 1;
    }
}

では、数学的帰納法の証明プログラムを再帰的に表現してみます。

void prove(int n) {
    if (n == 0) {
        printf("基底より、P(%d)が成り立ちます。\n", n);
    } else {
        // 再帰処理
        prove(n - 1);
        printf("帰納より「P(%d)が成り立つならばP(%d)も成り立つ」といえます。\n", n - 1, n);
        printf("したがって「P(%d)が成り立つ」といえます。\n", n);
    }
}

n が 0 以上の整数であるとき、0 から n までの整数の和を再帰的に定義するとどうなるでしょうか。