Re: help an o'caml beginner

[Michel Quercia <quercia@cal.enst.fr>]

Le Wed, 26 Jul 2000, John BEPPU a écrit :
> I tried out the recursive fibonacci number program
> ...
> Next, I tried to fumble my way through making an O'Caml version of
> this iterative algorithm, but I failed due to my lack of knowledge
> about this language.

Below are three translations of your iterative C code :

------------------------------------------------------------
(* iterative Caml code *)
let fib(n) =
  let a = ref(1) and b = ref(1) in
  for i=2 to n do
    let x = !a + !b in
    a := !b;
    b := x
  done;
  !b
;;

-------------------------------------------------------------
(* recursive Caml code, fib2(n) returns (fib(n-1),fib(n)) *)
let rec fib2(n) = 
  if n <= 1 then (n,1)
  else let (a,b) = fib2(n-1) in (b,a+b)
;;

let fib(n) = let (_,x) = fib2(n) in x;;

-------------------------------------------------------------
(* tail-recursive Caml code, fib3 a b n computes a*fib(n) + b*fib(n-1) *)
let rec fib3 a b n = if n <= 1 then a + b*n else fib3 (a+b) a (n-1);;
let fib(n) = fib3 1 0 n;;
--------------------------------------------------------

Note that there are also divide-and-conquer algorithms for computing Fibonacci
numbers that achieve logarithmic computing time with respect to the input.

> I wish the tutorial were available in HTML.

There is atutorial included in the html documentation.

Regards,
-- 
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://pauillac.inria.fr/~quercia
mailto:quercia@cal.enst.fr