-
-
Save chomado/9174376 to your computer and use it in GitHub Desktop.
| // 末尾再帰についての説明 | |
| /*********************************************************/ | |
| /* 処理概要: nの階乗を返す (Int -> Int) */ | |
| /* 目的: 普通の再帰で書いたものと、末尾再帰で書いたものの比較 */ | |
| /*********************************************************/ | |
| // =====普通の再帰===== | |
| int fact(int n) | |
| { | |
| if (n <= 0) | |
| return 1; | |
| else | |
| return n * fact(n-1); | |
| } | |
| // =====末尾再帰====== | |
| int fact( int n ) | |
| { | |
| return _fact( n, 1 ); | |
| } | |
| int _fact( int n, int a ) | |
| { | |
| if (n <= 0) { | |
| return a; | |
| } else { | |
| a *= n; | |
| return _fact( n-1, a ); | |
| } | |
| } | |
| /*********************************************************/ | |
| /* 処理概要: フィボナッチ数列の総和を求める(末尾再帰) */ | |
| /*********************************************************/ | |
| int fib(int n, int a = 0, int b = 1) | |
| { | |
| if(n <= 0) { | |
| return b - 1; | |
| } else { | |
| return fib(n - 1, b, a + b); | |
| } | |
| } | |
| // n番目のフィボナッチ数を返す関数 | |
| int sub_fib (int n, int a = 0, int b = 1) | |
| { | |
| if(n <= 1) { | |
| return a; | |
| } | |
| return sub_fib(n - 1, b, a + b); | |
| } |
@kotatsu_miさんから教えていただいたメモのコピペ:
うまく調整してreturnは単なる関数呼び出しだけにしてしまうのが末尾再帰.
末尾再帰はあくまで関数の最後でだけ再帰します
再帰の呼び出しが最後でなかったり，呼び出しだけじゃなくて別の処理が含まれていると，再帰から帰ってきて中断している処理を再開しなければなりませんが，
末尾再帰の場合は最後の呼び出しの後に一つ一つ再帰元に戻って作業を再開せずとも処理が終了してしまっています
すると，再帰ではなくただのループとかと同じように処理できるため, スタックなどの消費を減らしたりできるので最適化できるわけです．
実際，いくつかのコンパイラでは末尾再帰のものと判定されるとループに直してしまったりして最適化してるそうです
普通の再帰だと，n_fact()になっているのでfact()が終わったあとにn_の部分の計算をしなければならないので，fact()の呼び出したところに帰ってくる必要がありますね．ここでnが凄くおおきいと，再帰が深くなりすぎて関数の呼び出しを記憶するスタックメモリ(コールスタック)を消費しつくしてオーバーフローを起こし，最悪プログラムがエラーを吐いて停止します． そこで，末尾再帰のコードを見ると，returnの結果がそのまま答えになるのでわざわざ一つづつ呼び出し元に帰らなくても良いのです。
たとえば3をfact()に渡したときを考えます． まず，最初の再帰が呼ばれて3 * fact( 2 )になりますよね． そして次に呼び出されたときは3 * 2 * fact(1)，そして最後に3 * 2 * 1と展開されていきますよね? (末尾再帰ナシ)
ただ，展開されていくにあたって，n * fact(n-1)のn_の部分を記憶しておいて，fact(n-1)からreturnで帰ってきたときに記憶しておいた値をつかって処理する必要がありますよね
なので3でなく10000とか渡しちゃうとその数だけ変数を記憶しなければならないので，単純計算で32_10000バイト，関数は呼び出し元に帰るのに呼び出し元のアドレスも記憶せねばならないのでさらにメモリは消費します
ところが，末尾再帰だと再帰呼び出しするまえにもうn_の部分を計算してしまってaに格納して，次の関数に渡してしまっています．呼び出し元に帰らなくてもいいし余計な値を記憶する必要もありません。
3を渡しても，a=1_3を_fact()に渡して，次にa=1_3_2を_fact()に渡して，最後にreturn a=1_3_2*1になってますね．ここから処理としては呼び出し元にひとつづつ帰っていく必要がありますが，もう計算処理は終わってます。
するとコンパイラ自体が賢いと，末尾再帰なら呼び出し元に一つずつ戻るような処理を省くように最適化したりそもそも再帰じゃなくて単純なループに変換してしまえたりするので，末尾再帰のほうがメモリを消費せず済みます。
これなら，Cでも(コンパイラの最適化によっては)関数型言語みたいに死ぬほど再帰してもメモリがオーバーフローしてプログラムが死んだりしなくてすむことがあるのです。
基本的に，C言語のような言語では変数も引数もスタックにどんどんどんどん積まれます。 http://www.ipa.go.jp/security/awareness/vendor/programmingv1/b06_01.html の図3参考
それを念頭に置くと，再帰がなぜCのような言語だと相性わるくて，末尾再帰だと最適化しやすいのか，わかるかもしれません．考えてみてください
あ，最後にですが，私の説明いろいろと省きがちだったりしててちょっと"嘘をついている"かもしれないので，正確なところは自分であれこれ調べるのが良いとおもいます．あくまで参考程度に留めてくださいな
増やされた引数は「蓄積変数」(accumulator)と呼ばれる。
アキュムレータは「途中経過が計算できるならその時点の途中経過を先に計算して終わらせてしまう」もの。
（逆にそうじゃないものはアキュムレータが非常に不格好になる）
末尾再帰で何が美味しいか:
・普通の再帰だと、中断している処理を全て貯めるので、どんどんスタックが積まれますが、
・一方、末尾再帰だと、計算途中のものが破棄され、計算済みの各_fact( n, 1 )だけが保存されるから、でしょうか