我が内なるアジア

自己相似イヤリングを描く再帰関数を、仮想プログラミング言語で書いてみると下記のようになる。

1: 関数：イヤリングを描く（カウント） [
2:   顔を描く
3:   カウントをひとつ減らす
4:   もしカウントが０でなければ [
5:     関数：イヤリングを描くを呼んで左耳のイヤリングを描く(カウント）
6:     関数：イヤリングを描くを呼んで右耳のイヤリングを描く(カウント）
7:    ]もし条件ここまで
8: ] 関数ここまで

これをひとつひとつ追いながら見てみよう。
まず、この再帰関数をカウント＝3で呼んでみる。
これを「レベル１」と呼ぼう。

２行目で顔が描かれる。
３行目でカウントが一つ減り、2となる。
４行目では"0でなければ"に合うので５行目に進む。
５行目でカウント２でこの関数が呼ばれる。
これを「レベル２」と呼ぼう。

レベル２の２行目で顔が描かれる。
３行目でカウントが一つ減り、１となる。
４行目では"0でなければ"に合うので５行目に進む。
５行目でカウント１でこの関数が呼ばれる。
これを「レベル３」と呼ぼう。

レベル３の２行目で顔が描かれる。
３行目でカウントが一つ減り、０となる。
４行目では"0でなければ"に合わないので８行目まで進み、この関数から抜ける。
関数から抜けたら、この関数の呼び元のレベル２の５行目に戻り、６行目に進む。
今度は右耳を描くためにカウント１でこの関数が呼ばれる。
また「レベル３」になる。

レベル３の２行目で顔が描かれる。
３行目でカウントが一つ減り、０となる。
４行目では"0でなければ"に合わないので８行目まで進み、この関数から抜ける。
関数から抜けたら、この関数の呼び元のレベル２の６行目に戻り、７、８行目に進み、この関数から抜ける。

関数から抜けたら、この関数の呼び元のレベル１の５行目に戻り、６行目に進む。
今度は右耳を描くためにカウント２でこの関数が呼ばれる。
また「レベル２」になる。

。。。

と繰り返していくことで、自己相似イヤリングが描かれる。
この操作をもう一段深く、最初にカウント＝４でこの再帰関数を呼ぶと、最終形は下記のようになる。
以上のように、再帰関数での再帰的な呼び出しを順を追いながら見てみたが、ここで肝心なことは、プログラム中のどこにも、「ループ」という言葉が使われていない、ということである。

再帰関数は確かにループをするものであるが、そのループが再帰的であるため、一般的なループでは表せない入れ子構造を表すことができる。
これは、「多重ループは多次元を表している」という前回の話における「次元」とはまた違った意味での「次元」とでも言うべきものである。