ここ数日悩み続けていた末尾再帰について, もしかしたら意外と簡単なんじゃないかという答えが出たのでまとめておきます.
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減らす
これをカウンタが0になるまで繰り返してるだけですね.
じゃあこれを, 引数の中でやればいいんです.
もう一度末尾再帰版をお見せします.
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
が0
になれば第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
が0
になれば第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
どうでしたか?
思っていたより簡単だったんじゃないでしょうか?
実際にはこれよりもっと速い実装もあるらしいのですが, 今の僕にはまだ分かりません.
ここはこうした方が良い, 等の意見がありましたら是非コメントで教えて頂けるとありがたいです.