計算プロセス(計算過程)の種類に再帰的プロセスと反復的プロセスがあります。
他の多くの言語では反復的プロセスは繰り返し構文で書くのが当たり前ですが、
Schemeではどちらも「再帰的手続き」で書く事ができます。
|
| 再帰的プロセス
| 反復的プロセス
|
| 他言語
| 再帰的手続き(または繰り返し構文に書き直す)
| 繰り返し構文
|
| Scheme
| 再帰的手続き
| 再帰的手続き
|
Schemeプログラマにとって再帰は最も自然な考え方です。ところがこれは他の言語のプログラマにとっては非常識に見えるようです。他の言語のプログラマの文章を引用してみましょう。
結論として、階乗の計算には、再帰を使う必要は全然ないということである。 まあ、再帰を使っても計算できないことはない。そういう程度のことを、再帰の見本みたいに紹介する本とかがあるが、あれは完全に狂った世界である。
藤原博文「Cパズルプログラミング 再帰編」
http://karetta.jp/book-node/cpuzzle-recursion/001636
また、こんなことを主張する他の言語のプログラマもいます。
本質的に再帰的なものは再帰で、本質的に反復的なものはループ(繰り返し)で書くべき
これに対してSchemeプログラマはこんなことを思っています。
そんなの(再帰的プロセスでも反復的プロセスでも)どっちも「再帰的手続き」で書けるじゃん。何を騒いでるの?
Schemeの言語仕様を知ったとき、他の言語のプログラマはこう思うことでしょう。
繰り返し構文はdoしかないの? それで使い物になるの?
心配には及びません。Schemeプログラマはdoなんか使わないからです
。
繰り返しを書こうとしてdoの構文を覚えるのは無駄な努力です。心配せずに再帰を書きましょう。
(実はSchemeではdoも再帰的手続きとして書かれています。doを使っていても、知らず知らずのうちに再帰を使っていることになります)
再帰的プロセスと反復的プロセス
計算プロセス(計算過程)の種類に再帰的プロセスと反復的プロセスがあることを冒頭に述べました。
なぜ他の多くの言語では反復的プロセスを繰り返し構文で書くのが当たり前なのでしょうか?
それどころか、実装上の制限から再帰的プロセスを反復的プロセスに書き直してループで書くことすらあります。
Schemeではどちらも「再帰的手続き」で書く事ができます。
再帰的手続きとは何でしょうか?
- 再帰的手続きとは自分自身を手続き適用する手続きである
他の手続きを適用する代わりに自分自身を適用しているだけであり、ごく普通の手続きに過ぎません。
他の多くの言語で反復的プロセスをループ(繰り返し)構文で書かざるを得ないのは、末尾再帰を最適化していないからです。末尾再帰の最適化については本節の後半で説明します。
再帰的プロセスの例
「Cパズルプログラミング再帰編」の例にあった階乗計算を数式で表現するなら、
と書けます。階乗計算を再帰的プロセスとして計算してみましょう。
一つ前まで出来ていることにする
ここで一つ前まで出来ていることにするという法則を導入します。
すると階乗計算の数式は次の式に変形できます。
![n! = n\cdot[(n - 1)\cdot(n - 2)\cdot\cdot\cdot3\cdot2\cdot1] = n\cdot(n - 1)!](http://karetta.jp/images/3/factorial2.gif)
結論としては、階乗計算とはn-1の階乗にnを掛けたものです。
「計算機プログラムの構造と解釈第二版」ではこの性質を利用して、階乗を計算するfactrial手続きを次の通りに書いています。
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
factorial手続きはその最後に自分自身を適用しています。factorial手続きは「再帰的手続き」です。
置き換えモデルで計算を確かめる
factorial手続きがどうやって階乗を計算するかは置き換えモデルで確かめることができます。
(factorial 4)
↓
(* 4 (factorial 3))
↓
(* 4 (* 3 (factorial 2)))
↓
(* 4 (* 3 (* 2 (factorial 1))))
↓
(* 4 (* 3 (* 2 1)))
「一つ前の階乗計算」に順次置き換えていくことで4の階乗が計算できます。
これまで見たとおり、再帰的プロセスの例は対象となる問題の構造がすでに再帰的であった(「一つ前まで出来ている」ことにできる)と言えます。再帰的プロセスは素直に再帰的手続きとして書くことができます。
反復のための特別の構文を導入しなければならない欠点はSchemeにはない
他の言語では反復プロセスを表現するには特別の構文を必要としますが、Schemeにはこの欠点はありません。反復プロセスも再帰的プロセスもどちらも手続き呼び出しで表現できます。
by えんどうやすゆき
