とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

基数変換(3)

では Recur が何度も呼ばれたときに処理Aと処理Bがどのように行われるのでしょうか? 簡単なコードを走らせ,その実行結果を見て考えましょう。

#include <stdio.h>
void Recur(int n)
{
// 処理A
printf("処理A n = %d\n", n);

if (n < 3) Recur(n+1); // 再帰

// 処理B
printf("処理B n = %d\n", n);
}

int main(void)
{
Recur(0);
return 0;
}


実行結果:
処理A n = 0
処理A n = 1
処理A n = 2
処理A n = 3
処理B n = 3
処理B n = 2
処理B n = 1
処理B n = 0

処理Aが連続で実行され,その後,処理Bが逆に実行されているかのように見えます。ここで注意したいのは,最初に main から呼ばれた Recur の n と,main から呼ばれた Recur から呼ばれた Recur の n は,別の領域に確保され再帰が戻ってくるまでとっておかれるということです。つまり,Recur が再帰的に呼ばれ階層が異なれば,n も階層ごとに異なります。さらに Recur 内では n を変更していませんから,処理Aと処理Bにおいて n が等しければ同じ階層であることが分かります。
では次に,実行結果を同じ階層でそろえてみましょう。
main から呼ばれた Recur       処理A n = 0  ↓  ↑  処理B n = 0
↓ ↑
↑の Recur から呼ばれた Recur 処理A n = 1 ↓ ↑ 処理B n = 1
↓ ↑
↑の Recur から呼ばれた Recur 処理A n = 2 ↓ ↑ 処理B n = 2
↓ ↑
↑の Recur から呼ばれた Recur 処理A n = 3 ↓ ↑ 処理B n = 3
→→↑

さらに,前回紹介した123を2進表記するための計算方法を思い出してください。

2)123 計算。商(61)を同じ処理に渡す。余りを保存。 ↓ ↑ - 1 余りを出力
2) 61 計算。商(30)を同じ処理に渡す。余りを保存。 ↓ ↑ - 1 余りを出力
2) 30 計算。商(15)を同じ処理に渡す。余りを保存。 ↓ ↑ - 0 余りを出力
2) 15 計算。商( 7)を同じ処理に渡す。余りを保存。 ↓ ↑ - 1 余りを出力
2) 7 計算。商( 3)を同じ処理に渡す。余りを保存。 ↓ ↑ - 1 余りを出力
2) 3 計算。商( 1)を同じ処理に渡す。余りを保存。 ↓ ↑ - 1 余りを出力
2) 1 計算。商( 0)。同じ処理をしない。余りを保存。↓ ↑ - 1 余りを出力
→→↑

よく似ていますね。一行が一つの関数となります。「商を同じ処理に渡す」ことによって再帰が起こります。具体的にC言語に起こすと:
void PrintBinary(int n)
{
// 1. 2で割り,余りを横に書く。
// div_t div(割られる数, 割る数);
// div_t.quot は商(quotient)
// div_t.rem は余り(remainder)
div_t d;
d = div(n, 2);

// 2. それを商が 0 になるまで続ける。
if (d.quot) PrintBinary(d.quot);

// 3. 余りを下から読む。
static const char s[] = "01";
putchar(s[d.rem]);
}


となります。
次回以降でこのコードの修正をします。みなさんもコンパイルが通るようにしたり,main を追加するなどしてみましょう。さらに adic進数に一般化するにはどうしたらよいのかも考えてみましょう。


独り言:データ構造のスタックを実装しなくても,スタックを実現できるのが再帰の強みですね。