OCaml と末尾再帰

末尾再帰とは各再帰処理で、計算結果と再帰処理を行い、再帰の末端ですぐ計算結果を返せる状態になっていること。
詳しくは以下の回答 2 を参照ください。

In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of "(return (recursive-function params))" (I think that's the syntax for Lisp). Basically, the return value of any given recursive step is the same as the return value of the next recursive call.

The consequence of this is that once you are ready to perform your next recursive step, you don't need the current stack frame any more. This allows for some optimization. In fact, with an appropriately written compiler, you should never have a stack overflow snicker with a tail recursive call. Simply reuse the current stack frame for the next recursive step. I'm pretty sure Lisp does this.

http://stackoverflow.com/questions/33923/what-is-tail-recursion

OCaml と末尾再帰

んで、そもそもの末尾再帰は OCaml に触れていた時に知ったことなんだ。

具体的には以下のコード

OCaml 4.01.0 で動かしたけど、それ以前のコードでも動くんじゃないかと感じます。

#! /usr/bin/env ocaml

(* echo *)
let echo msg = print_string (msg ^ "\n");;

(* 配列の長さを取得 *)
(* 通常バージョン *)
let rec length0 ls =
    if (ls = []) then 0
    else (1 + length0 (List.tl ls))
;;

(* 末尾再帰バージョン *)
let length1 ls =
    let rec iter n ls =
        if (ls = []) then n
        else (iter (n + 1) (List.tl ls)) in
    iter 0 ls
;;

(* 対象 *)
let length = length0;;
echo "対象: length0";;

(* length 呼び出しをトレース *)
#trace length;;

let ls = [1; 2; 3; 4; 5; 6; 7; 8; 9];;
echo ("The result is: " ^ (Printf.sprintf "%d" (length ls)));;

リストの長さを返す関数を書いているけど、length0 が普通の関数。 length1 が末尾再帰の関数。

length1 を見ると分かるように、各再帰処理で現状の計算結果を保持しており、 ls が空配列 [] になったら n が変えるようになっている。

この場合、各再帰処理をスタックに積まなくても n がわかっており、途中の再帰処理をスタックに積まなくても良いよねとわかる。

便利。

具体的に、 #trace some;; で関数の呼び出しを見ることができるけど、 length0 と length1 の結果は以下となる。

なんか末尾再帰最適化 (tail call optimization) が効いてくれて、うれしい感じになった、便利。

length0 の実行結果

$ ./hoge
対象: length0
length is now traced.
length <--
  [; ; ; ; ; ; ; ; ]
length <-- [; ; ; ; ; ; ; ]
length <-- [; ; ; ; ; ; ]
length <-- [; ; ; ; ; ]
length <-- [; ; ; ; ]
length <-- [; ; ; ]
length <-- [; ; ]
length <-- [; ]
length <-- []
length <-- []
length --> 0
length --> 1
length --> 2
length --> 3
length --> 4
length --> 5
length --> 6
length --> 7
length --> 8
length --> 9
The result is: 9

length1 の実行結果

$ ./hoge
対象: length1
length is now traced.
length <--
  [; ; ; ; ; ; ; ; ]
length --> 9
The result is: 9