練習問題 3.10
(* 練習問題 3.10 *)
(* fib 4 の値呼び出しによる評価ステップを fact 4 の例にならって示しなさい。 *)
(*
フィボナッチ数列
1 2 3 4 5 6 7 8 9 10 11 12
1 1 2 3 5 8 13 21 34 55 89 144
*)
let fib n =
let rec fib_pair n =
if n = 1
then (1, 0)
else
let (i, j) = fib_pair (n - 1) in
(i + j, i)
in
let (i, _) = fib_pair n in
i;;
(* TEST *)
let test1 = fib 4 = 3;;
let test2 = fib 7 = 13;;
let test3 = fib 12 = 144;;
(*
fib 4 = fib_pair 4 = (if 4=1) fib_pair 3 = (L, R) => (L+R, L) = L+R
fib_pair 3 = (if 3=1) fib_pair 2 = (L, R) => (L+R, L) = L+R
fib_pair 2 = (if 2=1) fib_pair 1 = (L, R) => (L+R, L) = L+R
fib_pair 1 = (if 1=1) (1, 0) => 1
fib_pair 2 = (1, 1) => 1
fib_pair 3 = (2, 1) => 2
fib_pair 4 = (3, 2) => 3
*)
関連