LoginSignup
11

More than 5 years have passed since last update.

再帰を末尾再帰に変換する基本ステップ

Last updated at Posted at 2016-03-06

すごい H 本で何かに目覚めた俺達は、偶然にもすごい E 本を手にしていた。

〜関数型言語殺人事件序文〜

はじめに

再帰を末尾再帰に変換する際に、頭がこんがらがってキツかったので、もしや何か基本手順があるのではないかと思い、考えてまとめてみました。

再帰と末尾再帰を変換する少数例をボケっと眺めてて思いついた自己流の基本ステップなので、おかしな箇所がありましたら指摘をお願いします。

基本ステップ

  1. アキュムレータの初期値を考える
    • 元の再帰の終了条件の右辺から決定する
  2. 終了条件を考える
    • アキュムレータの初期値と元の再帰の終了条件を照らし合わせる
  3. 一般式を考える
    • アキュムレータの値の計算は元の再帰の一般式を参考にする

サンプル

2つの簡単な問題で再帰を末尾再帰に変換してみたいと思います。

リストの長さを取得する関数

まずは通常の再帰で書いてみます。

len([]) -> 0;
len([_|T]) -> 1 + len(T).

では、変換していきます。

1. アキュムレータの初期値を考える

元の再帰の終了条件の右辺を見たところ、0ですね。

tail_len(L) -> tail_len(L, 0).

tail_len/1が外側に公開するインタフェースです。
tail_len/2が実際にアキュムレータを導入して末尾再帰化されたlen/1になります。

2. 終了条件を考える

リストのサイズが0になったときに終了します。
この時に返される値はlen([]) -> 0;より、0とわかります。

tail_len([], Acc) -> Acc;

アキュムレータの初期値が0ですので、それをそのまま返せば OK です。

3. 一般式を考える

len([_|T]) -> 1 + len(T).を元に一般式を考えます。
今回は、アキュムレータの次の値は元のロジックをそのまま適用すれば大丈夫です。

tail_len([_|T], Acc) -> tail_len(T, 1 + Acc).

次に受け取るリストは、元のリストから1つ減らしたものを渡せば良いので、T をそのまま渡します。

最終形

以上、3ステップで末尾再帰化は完了です。

tail_len(L) -> tail_len(L, 0).

tail_len([], Acc) -> Acc;
tail_len([_|T], Acc) -> tail_len(T, 1 + Acc).

みんな大好きフィボナッチ数列

みんな大好きフィボナッチ数列の定義をそのまま書き下してみます。

fib(1) -> 0;
fib(2) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

見慣れたアレですね。

1. アキュムレータの初期値を考える

まず、元の再帰の一般式を見たところ、2つ再帰呼び出しがあります。
というわけで、アキュムレータは2個準備しておきます。

tail_fib(N) -> tail_fib(N, 0, 1).

初期値は元の終了条件の右辺からそのまま持ってきています。

2. 終了条件を考える

元の終了条件からそのまま、末尾再帰での終了条件を書いてみます。

tail_fib(1, Acc1, _) -> Acc1;
tail_fib(2, _, Acc2) -> Acc2; % 実は不要

ホントにこれでいいのかよって気がしますが、多分大丈夫です。多分。
そして2つ目の終了条件は実は不要ですが、ここでは放置します。

3. 一般式を考える

混乱を防ぐために、それぞれのアキュムレータが何を意味しているのか抑えておきます。今回はAcc1 = fib(N-2)Acc2 = fib(N-1)という意味になっています。

すなわち次のアキュムレータは、元の一般式のfib(N) -> fib(N-1) + fib(N-2).から考えると、

  • NextAcc1 = fib(N-1) = Acc2
  • NextAcc2 = fib(N) = Acc1 + Acc2

となります。

よって、一般式は、

tail_fib(N, Acc1, Acc2) -> tail_fib(N-1, Acc2, Acc1+Acc2).

となります。

最終形

以下の通りになりますが、 まだ 実は不要 と書いたものが残っています。

tail_fib(N) -> tail_fib(N, 0, 1).

tail_fib(1, Acc1, _) -> Acc1;
tail_fib(2, _, Acc2) -> Acc2; % 実は不要
tail_fib(N, Acc1, Acc2) -> tail_fib(N-1, Acc2, Acc1+Acc2).

tail_fib(2, _, Acc2) -> Acc2;が何故不要かについては、tail_fib(N, Acc1, Acc2)N=2を代入して見ればわかるかと思います。

試しに入れてみるとtail_fib(2, Acc1, Acc2) -> tail_fib(1, Acc2, Acc1+Acc2)となり、結局Acc2が返ってくることがわかります。

というわけで、

tail_fib(N) -> tail_fib(N, 0, 1).

tail_fib(1, Acc1, _) -> Acc1;
tail_fib(N, Acc1, Acc2) -> tail_fib(N-1, Acc2, Acc1+Acc2).

これで完成です。

まとめ

末尾再帰をいきなり考えるのではなく、再帰から考えたほうが良さそうです。
元の再帰を元に、初期値、終了条件、一般式と考えると混乱が少ないように思います。
また、元の再帰を考える際も、終了条件から考えると考えやすい気がします。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
11