ここ数日悩み続けていた末尾再帰について, もしかしたら意外と簡単なんじゃないかという答えが出たのでまとめておきます.
Haskellによる末尾再帰の情報は思いの外少なく, かなり苦戦しました.
例によって書いてるのは初心者です. 間違い等あればご指摘頂けるとありがたいです.
末尾再帰とは何ぞや？という話
末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。再帰にかかわらず一般に、そのような最後の呼び出しを末尾呼び出し （en:Tail call）という。呼び出しではなく、戻り先を保存しないジャンプに最適化できるという特徴がある。
出典:Wikipedia日本語版 末尾再帰
だそうです.
普通の再帰にするとスタックを馬鹿食いするので, 処理が重くなるらしい.
一方, 末尾再帰にすると使うスタックの量が減るので, 処理がとても軽いとのこと.
実際, 体感で重いなと感じる程には差が出ていました.
再帰の例
階乗
再帰の例によく用いられる階乗を作っていきたいと思います.
fact :: Int -> Int
fact 0 = 1
fact n = n * (fact $ n - 1)
これに例えば4を引数に渡すと,
fact 4
↓
4 * (fact 3)
↓
4 * (3 * (fact 2))
↓
4 * (3 * (2 * (fact 1)))
↓
4 * (3 * (2 * (1 * (fact 0))))
↓
4 * (3 * (2 * (1 * (1))))
↓
4 * (3 * (2 * (1)))
↓
4 * (3 * (2))
↓
4 * (6)
↓
24
このような演算過程を経て, 階乗の結果を得られる事ができます.
一通り広げ晒してから演算を行うため, 処理は重くなります.
次に末尾再帰版です.
fact :: Int -> Int
fact n = fact' n 1
where
fact' 0 y = y
fact' x y = fact' (x - 1) (x * y)
こちらにも同様に4を渡してみます.
fact 4
↓
fact' 4 1
↓
fact' 3 4
↓
fact' 2 12
↓
fact' 1 24
↓
fact' 0 24
↓
24
こうなります.
処理数も少なく, 一度出てきた演算はその時に終わらせているので非常に軽いです.
末尾再帰の考え方
僕の中で出た結論は, 手続き型の時同様に考えるでした.
手続き型言語でwhile文やfor文を使って計算する, あの時と同じ感覚です.
具体的に説明していきます.
int fact(int num) {
int result = 1;
while (num) {
result = result * num; //再帰のように見せるため, あえて*=は使用せずこちらの書き方にしています
num--;
}
return result;
}
手続き型的に書くとこうなりますね.
これとほぼ同じ考え方で行けるんです.
この手続き型のプログラムの中には
- カウンタ
- 演算に必要な値
- 計算結果
の3つがあります.
今回の場合は,
- カウンタ →
num - 演算に必要な値 →
num - 計算結果 →
result
となっています.
今回は階乗なので演算に必要な値とカウンタは同一の変数です.
やってる内容としては,
- 計算結果入力用の変数
resultを単位元で初期化 - 計算結果入力用の変数
resultと演算に必要な値numを掛け合わせ, 結果を計算結果入力用の変数resultに代入 - カウンタ
numを1減らす
これをカウンタが０になるまで繰り返してるだけですね.
じゃあこれを, 引数の中でやればいいんです.
もう一度末尾再帰版をお見せします.
fact :: Int -> Int
fact n = fact' n 1
where
fact' 0 y = y
fact' x y = fact' (x - 1) (x * y)
- まずは演算に必要な値であり, カウンタでもある定数
nをfactの引数から受け取り, ローカル関数fact'の第1引数xに渡し,fact'の第2引数である計算結果入力用の引数yを単位元で初期化する - 自分自身を再帰呼び出しし, カウンタ
nを1減らした値を第1引数xに, 演算に必要な値xと計算結果入力用の引数yを掛け合わせた結果を第2引数に渡す
これを繰り返し, カウンタnが０になれば第2引数yを計算結果として返しているだけです.
どうですか？
この考え方, かなり手続き型ちっくな気がしませんか？
他の例
累乗
次は累乗を求める関数powです.
pow :: Int -> Int -> Int
pow a b = pow' a b 1
where
pow' a 0 c = c
pow' a b c = pow' a (b - 1) (a * c)
powの場合は演算に必要な値とカウンタがそれぞれ違うため, 引数がもう1つ増えます.
ですが, 引数が増えただけでやっている事は基本的に同じです.
- まずは演算に必要な値
aをpowの第1引数から受け取り, ローカル関数pow'の第1引数に渡し, カウンタである定数bをpowの第2引数から受け取り, ローカル関数pow'の第2引数xに渡す.pow'の第3引数である計算結果入力用の引数yは単位元で初期化する - 自分自身を再帰呼び出しし, 演算に必要な値
aは不変なのでそのまま第引数に渡し, カウンタbを1減らした値を第2引数xに, 演算に必要な値aと計算結果入力用の引数cを掛け合わせた結果を第3引数に渡す
これを繰り返し, カウンタbが０になれば第1引数aを計算結果として返します.
実行過程は以下の通りです.
pow 2 4
↓
pow' 2 4 1
↓
pow' 2 3 2
↓
pow' 2 3 4
↓
pow' 2 1 8
↓
pow' 2 0 16
↓
16
フィボナッチ数列
最後にフィボナッチ数列です.
きっと僕はこれを記事の中に書かないと落ち着かないんです.
ここまで来るともうきっと読めるはずですし, 見る前にも書けるんじゃないでしょうか？
fib n = fib' n 1 1
where
fib' n x y
| n == 0 = 1
| n == 1 = x
| otherwise = fib' (n - 1) (x + y) (x)
実行過程は以下の通りです.
fib 5
↓
fib' 5 1 1
↓
fib' 4 2 1
↓
fib' 3 3 2
↓
fib' 2 5 3
↓
fib' 1 8 5
↓
8
どうでしたか？
思っていたより簡単だったんじゃないでしょうか？
実際にはこれよりもっと速い実装もあるらしいのですが, 今の僕にはまだ分かりません.
ここはこうした方が良い, 等の意見がありましたら是非コメントで教えて頂けるとありがたいです.