再帰関数呼び出しの評価

再帰関数呼び出しの評価は、再帰でない関数呼び出しの評価と比べてもそう難しくはありません。 フィボナッチ数を計算する関数として fib を次のように定義しましょう:

fun fib
  (n: int): int =
  if n >= 2 then fib(n-1) + fib(n-2) else n
// end of [fib]

さらに ENV0 の下で fib(3) を評価してみましょう; n と 3 の間に束縛を作り ENV0 を ENV2 に拡張した後、 ENV2 の下で fib の本体の評価を開始します; それから ENV2 の下で fib(n-1) + fib(n-2) の評価に辿り着きます; ENV2 の下で fib(n-1) を評価して ENV2 の下で fib(2) の評価を導き、結局 1 を返します; ENV2 の下で fib(n-2) を評価して ENV2 の下で fib(1) の評価を導き、結局 1 を返します; したがって ENV0 の下で fib(3) を評価すると(1+1 の結果) 2 が返ることになります。