K&Rを読もう(8) 1.7 図解Schemerの再帰脳

GCC

Schemerは再帰が無いと生きていけない。再帰で考えた方がシンプルに問題が解ける。

K&R 1.7のテーマはべき乗。丁度良い題材なので、Schemerの再帰脳を復習しておこう。

Schemerは再帰で考える。

2の10乗をやろう。

2の10乗。つまり、2を10回掛けるってこと。

展開してみる。

power(2, 10) = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

2のゼロ乗は1だから、1を掛ける。

power(2, 10) = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 1

こんな感じ。

色々やってみよう。

power(2, 10) = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 1
power(2, 9)  = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 1
power(2, 8)  = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 1
power(2, 7)  = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 1

...(略

power(2, 2)  = 2 * 2 * 1
power(2, 1)  = 2 * 1
power(2, 0)  = 1

再帰的ですねぇ。

よく見てみるとパターンのある再帰的構造であることがわかる。

power(2, 10) = 2 * power(2, 9)
power(2, 9)  = 2 * power(2, 8)
power(2, 8)  = 2 * power(2, 7)
power(2, 7)  = 2 * power(2, 6)

...(略

power(2, 2)  = 2 * power(2, 1)
power(2, 1)  = 2 * power(2, 0)
power(2, 0)  = 1

power(2, 10) = 2 * power(2, 9)のように、一個前の結果を見れば良いことがわかる。数学っぽくすると、

power(base, 0) = 1
power(base, n) = base * pow(base, n - 1)

baseは基数、nは何乗するか。

ゼロの時は1で、nの時は(n - 1)の結果と掛ける。

後はプログラムに直すだけ。

// 再帰
int power_r(int base, int n)
{
    if (n == 0)
        return 1;
    return base * power_r(base, n - 1);
}

数学の定義と一緒だし、考え方もシンプルだ。

Schemerはこう考える。

  • 「一個前はなんだっけ」
  • 「終わりはなんだっけ」

それだけ考えれば良い。

for文に直すまでの道のり

僕の脳の中身をプログラムに置き換えてみる。

#include <stdio.h>
#include <stdlib.h>

// 再帰
int power_r(int base, int n)
{
    if (n == 0)
        return 1;
    return base * power_r(base, n - 1);
}

// 反復
int power_i(int base, int n)
{
    int iter(int p, int i)
    {
        if (i == 0)
            return p;
        return iter(p * base, i - 1);
    }
    return iter(1, n);
}

// 繰り返し(while)
int power_w(int base, int n)
{
    int p = 1;
    while ( n > 0) {
        p = p * base;
        --n;
    }
    return p;
}

// 繰り返し(for)
int power_f(int base, int n)
{
    int p = 1;
    for (; n > 0; --n)
        p = p * base;
    return p;
}

int main(void)
{
    int i;
    printf("%d\n", power_r(2, 10));
    printf("%d\n", power_i(2, 10));
    printf("%d\n", power_w(2, 10));
    printf("%d\n", power_f(2, 10));

    exit(EXIT_SUCCESS);
}

for文はフクザツ。

Schemerが再帰で考える訳がわかったかなぁ?