初めての人のためのLisp (再帰関数)
もう一度、再帰関数について。
Lisp特有の話ではないようにも思うが、これまであまり詳しくやったことがないので。
再帰関数とは、関数定義の中でその関数自体を呼び出すような関数。
よく、フィボナッチ数列とか表現するのにつかわれたりして、
数学的帰納法と対応づけられて話されることが多い。
しかし、Lispでは、リストを順に処理するような場合でも、
この考え方を利用する。
そのような場合は、帰納的と考えるよりも、ループと考えて実際にリスト(配列)を入れた時の挙動を考えるとよさそう
というのが個人的な感想。
その上で、
atom と リスト で場合分けしたり
さらに、終端で場合分けしたりして、
ループをつくる。
再帰関数の中でも、
末尾再帰という話がある。
これは、関数定義の中で、その関数が再帰的に呼ぶれてループが形成される場合、現在のループの結果がその関数自身のようなものをいう。
つまり、
(reverse (x c)
....
(t (reverse (cdr x) (cons (car x) c) )
のようなもの。
上記の変数cのように、累積変数や、外部の変数に値を入れることで、このような末尾再帰を作ることができる。
末尾再帰では、xやcにリストを適当に渡してみるとわかると思うが、
現在のループで、結果として返ってくる (reverse (cdr x) (cons (car x) c) の引数は全部決まる。
そのため、次のループに処理を完全に移行できる。
一方、普通の再帰関数は、
(reverse (x)
....
(t (cons (car x) (reverse (cdr x)) ))
みたいな感じになる。
これは、cons が現在のループの結果。
そのため、xに適当なリストを入れてみるとわかると思うが、
このループの結果になる、cons の引数は決まらない。
そのため、このcons という関数は評価待ちになる。
つまり、末尾再帰と普通の再帰の違いは、
現在のループの結果が評価可能か、評価待ちになるか というイメージのよう。
末尾再帰のようなものは、コンパイラが効率的に処理できるように実装されていることが多いので、推奨される。
普通の再帰は、本当に、評価待ちになったものが、終端が分かった時点で、逆向きに評価されるので、再帰という言葉がぴったりに思うけど、
末尾再帰って、順番に次のループで評価するので、単純なループというイメージが適当そう。
