我が内なるアジア

「再帰関数によって自分自身を呼ぶ」というのはどういう時に必要になるのだろうか？
たとえばこのブログで度々出てくる、"GNU's Not Unix!"である。

「GNUは何の頭文字を取ったものか？」というものを展開する関数がある、とする。
この関数は、与えられた文字列に"GNU"というものが見つかれば、それを説明するために、カッコ（）つきで"GNU's Not Unix!"という言葉に置き換える。
仮想プログラミング言語で書くと以下だ。

1: 関数"GNUを展開する"(文字列)[
2:　もし文字列に"GNU"が含まれていたらその後ろに"(GNU's Not Unix!)"と付け加える
3:    その文字列を返す
4: ]関数"GNUを展開する"ここまで 

この関数に"GNU"という文字列を与えると、"GNU(GNU's Not Unix!)"と返ってくる。

このプログラムの３行目で文字列を返さずに、もう一度その新しい文字列で自分自身を呼ぶとどうなるだろうか？ 

1: 関数"GNUを展開する"(文字列)[
2:　もし文字列に"GNU"が含まれていたらその後ろに"(GNU's Not Unix!)"と付け加える
3:    関数"GNUを展開する"(文字列)を呼ぶ
4: ]関数"GNUを展開する"ここまで 

このままだと、関数が自分自身を呼んで、さらに自分を呼んで、、、を繰り返すので無限ループである。
なので、この関数にはカウントダウンする数字を渡すことにして、決められた回数で止まるようにする。

1: 関数"GNUを展開する"(文字列, 数字)[
2:　もし文字列に"GNU"が含まれていたらその後ろに"(GNU's Not Unix!)"と付け加える
3:    もし数字が0ならば [
4:      文字列を返す
5:     ]
6:    そうでなければ [
7:      数字をひとつ減らす
8:      関数"GNUを展開する"(文字列, 数字)を呼ぶ
9:    ]
10: ]関数"GNUを展開する"ここまで
11: 文字列を返す

この関数("f0"と呼ぶ）を（"GNU", 2）という文字列と数字で呼ぶと、
２行目で"GNU(GNU's Not Unix!)"に書き換えられる。
3行目で数字は２なので、６行目までとぶ。
7行目で数字が１になる。
8行目でふたたびこの関数が("GNU(GNU's Not Unix!)", 1)で呼ばれる。

呼ばれた先("f1"と呼ぶ）では、
２行目で"GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)"に書き換えられる。
3行目で数字は1なので、６行目までとぶ。
7行目で数字が0になる。
8行目でふたたびこの関数が("GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)", 0)で呼ばれる。

さらに呼ばれた先("f2"と呼ぶ）では、
２行目で"GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)(GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)'s Not Unix!)"に書き換えられる。
3行目で数字は0なので、この文字列"GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)(GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)'s Not Unix!)"を返す。つまりf1に戻る。

f1では、
10行目で関数が終わるので、f0に戻る（"GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)(GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)'s Not Unix!)"を返す）。

f0では
10行目で関数が終わるので、
10行目で関数が終わるので、"GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)(GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)'s Not Unix!)"を返す。

再帰関数では以上のようなことが起こる。
ややこしい話だが、このようなややこしい問題を人間に代わってやってくれるのがコンピューターである。