JavaScriptを有効にしてください

OCamlとTail Call

 ·  ☕ 2 min read

末尾再帰について一度整理しておく.
OCaml, Haskell, Scala など多くの関数型言語の処理系は末尾再帰を最適化.

1
2
3
4
5
6
7
8
fn f(x: T) {
    if isTrue(hoge) { // not 末尾呼び出し
        return g(); // 末尾呼び出し
    }
    else {
        return x * h(); // not 末尾呼び出し
    }
}
1
2
3
4
5
6
7
8
fn f(x: T) {
    if isTrue(hoge) {
        return f(x); // 末尾再帰
    }
    else {
        return x * f(x); // not 末尾再帰
    }
}

→ 末尾再帰はコールスタックを食いつぶさない

  • コールスタック

通常のプログラムの実行モデルでは、関数を呼び出すと、関数自身のローカル変数(引数や局所変数)や戻り先情報を保持するスタックフレーム(アクティベーションレコード)が生成されてコールスタックと呼ばれるスタックにpushされます。

→ 末尾再帰だとそのままスタックフレームを再利用できる
(末尾再帰じゃないと再利用できない)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 階乗を計算する関数(末尾再帰バージョン)
function factorial(n) {

    // 末尾再帰関数
    function factorialTailCall(n, accum) {
        if (n === 0) {
            return accum;
        }
        return factorialTailCall(n - 1, n * accum); // 自分自身を末尾呼び出し
    }

    var result = factorialTailCall(n, 1);

    return result;
}

console.log(factorial(3));
  • OCamlの例
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# let rec f n =
    let rec iter i =
      if i < n then begin
        print_int i;
        iter (i + 1)
      end
    in
    iter 0;;

val f : int -> unit = <fun>

参考: https://qiita.com/pebblip/items/cf8d3230969b2f6b3132#末尾呼び出しと末尾呼び出し最適化

共有

YuWd (Yuiga Wada)
著者
YuWd (Yuiga Wada)
機械学習・競プロ・iOS・Web