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

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

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

実際、階乗を再帰的に定義しようと思ったとき、0! = 1 じゃないと矛盾が生じてしまうのです。

階乗の再帰的定義

まず「階乗」についての復習です。

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

実は階乗も再帰的に定義することができます。
たとえば階乗 n! がある場合、以下のような再帰的な定義が可能です。

具体的な階乗で考える

本当に再帰的な構造が存在するのか、具体的な階乗で検証してみましょう。

0! 以外は (n - 1) の答えを再利用していることがわかりますね。
また、再帰的な構造が成立させるには「 0! が 1 じゃないと辻褄が合わない」ことも分かります。

数学的帰納法との関連性

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

階乗の再帰的定義で最初に 0! が 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);
    }
}

prove(n - 1); していることから「大きなものから、段々と小さいもの」に進むことが分かります。

「和の定義」を再帰的に定義する

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

0 から n までの整数の和を S(n) としましょう。
S(n) を再帰的に定義すると以下のようになります。

S(n) の閉じた式

この問題に閉じた式も添えると S(n) = (n * (n + 1)) / 2 となります
これは以前「ガウス少年の主張」問題で解説しています。詳しくはそちらを参照してください。

CS シリーズ

次回

前回