再帰は再帰なんかじゃない！末尾再帰こそが真の再帰なんだ！「計算機プログラムの構造と解釈」で末尾再帰というものを知ったので勉強しました。自分の理解を書いてみます。 再帰 再帰呼び出しとはある手続きの中で、再びその手続き自身を呼び出すことと定義される1。でもこの定義は正確じゃない。なぜなら再帰呼び出しは自分自身を呼んでいないからだ。 階乗を考えてみよう。階乗は数学的にこう定義できる。 ふつうRubyで階乗メソッドはこう書く。 factメソッドの中でfactメソッドが呼ばれているので、自分自身が呼ばれているように見える。でもそうじゃない。 最初の引数5を受け取ったfactメソッド(彼をfact5と呼ぼう)は、引数4と共に自分が呼んだfactメソッド(fact4)の結果を待たなきゃならない。なぜならその結果と5をあとで掛けなきゃならないからだ。fact4もfact3もfact2も同じだ。自分が呼んだメソッドの結果を待たなきゃならない。 人間が待ちながら
