OCaml => テール再帰

前書き

OCamlのような関数型言語は再帰関数に大きく依存する。しかし、このような関数は、メモリの消費を超過したり、大きなデータセットを処理するときにオーバーフローをスタックする可能性があります。

このような場合、テール再帰は最適化の重要なソースです。これは、再帰呼び出しが関数の最後である場合に、プログラムが呼び出し元コンテキストを削除することを可能にします 。

以下は、整数のリストの合計を計算する非テール再帰関数です。

let rec sum = function
  | [] -> 0
  | h::t -> h + (sum t)

関数が最後に実行する操作は加算です。したがって、関数は末尾再帰的ではありません。

以下は同じ関数のテール再帰的バージョンです。

let sum l =
  let rec aux acc = function
    | [] -> acc
    | h::t -> aux (acc+h) t
  in
  aux 0 l

ここで、 aux関数はtail-recursiveです。最後に実行する操作は、それ自身を呼び出すことです。結果として、 sumの後者のバージョンは任意の長さのリストとともに使用することができます。

Modified text is an extract of the original Stack Overflow Documentation

ライセンスを受けた CC BY-SA 3.0

所属していない Stack Overflow