SICPより反復と再帰 #C


#include <stdio.h>

int Sum0(int start, int end)
{
    int sum = 0;
    for( ; start <= end ; ++start)
    {
        sum += start;
    }
    return sum;
}

int Sum1(int start, int end)
{
    if(start <= end)
    {
        return start + Sum1(start + 1, end);
    }
    else
    {
        return 0;
    }
}

int Sum2(int sum, int start, int end)
{
    if(start <= end)
    {
        return Sum2(sum + start, start + 1, end);
    }
    else
    {
        return sum;
    }
}


int main(int argc, const char * argv[])
{
    printf("%d\n", Sum0(1, 5));
    printf("%d\n", Sum1(1, 5));
    printf("%d\n", Sum2(0, 1, 5));


    /*
     Sum1(1, 5)
     = 1 + Sum1(2, 5)
     = 1 + 2 + Sum1(3, 5)
     = 1 + 2 + 3 + Sum1(4, 5)
     = 1 + 2 + 3 + 4 + Sum1(5, 5)
     = 1 + 2 + 3 + 4 + 5 + Sum1(6, 5)
     = 1 + 2 + 3 + 4 + 5 + 0
     = 15

     Sum2(0, 1, 5)
     = Sum2(0 + 1, 1 + 1, 5) = Sum2(1, 2, 5)
     = Sum2(1 + 2, 2 + 1, 5) = Sum2(3, 3, 5)
     = Sum2(3 + 3, 3 + 1, 5) = Sum2(6, 4, 5)
     = Sum2(6 + 4, 4 + 1, 5) = Sum2(10, 5, 5)
     = Sum2(10 + 5, 5 + 1, 5) = Sum2(15, 6, 5)
     = 15;
     */
    return 0;
}

SICPからのネタです。
1から5の合計を愚直に求める関数をテーマに反復と再帰の構造を考えてみます。
非常に面白いです。こんな考え方があったとは。
誰にでも分かるようにメモします。

まず、すごく手続き型的に考えて、Sum0があります。
for文をつかったまあ分かりやすいプログラムですね。これはいいでしょう。

次に再帰的な関数呼び出しです。
これは少々再帰関数に慣れていないと読みづらいと思います。
しかしこれは展開すると簡単にわかります。

Sum1(1, 5)
を呼び出すということは、次に
1 + Sum1(2, 5)
と展開することができます。そして次に
1 + 2 + Sum1(3, 5)
と、このようにどんどん展開していくことができます。
最後はSum1(6, 5)これは0になるようにifで仕込んであるので、
= 1 + 2 + 3 + 4 + 5 + 0
と展開されるので15になるわけですね。

さて、次が面白いです。
一つ引数が増えています。sumですね。
これは、関数を呼ぶたびに加算した上でスタックに積み続けます。
日本語にするとわけがわからないよ、となりますね。
なので、これも展開してみます。

Sum2(0, 1, 5)
これは次の関数を呼び出すときに２つのことを行います。
１、sumにstartを足す
２、startに1を足す
すると、
Sum2(1, 2, 5)
となります。
これはつまり、ここのsumは、関数Sum0のsum変数とほぼ同等の役割を果たしているわけです。計算をしながら次の関数を呼び出しているんですね。
「再帰関数ではあるが、反復的な構造をしている」
というちょっと不思議な気分です。　
同じ再帰関数でありながら、Sum1とSum2はまったく違う構造で問題を解決しているんですね。実に面白いと思いませんでしょうか。