Re: help an o'caml beginner

["Laurent Chéno" <lcheno@cybercable.fr>]

Le 26/07/00 à 11:51, beppu@lineo.com (John BEPPU) écrivait :

> Hi.

--- Please excuse my poor english --- 
> 
> Next, I wrote an iterative C version.
> 
>     #include <stdio.h>
> 
>     int fib(int n)
>     {
>         int val = 2;
>         int n1 = 2;
>         int n2 = 1;
>         int i;
>         if (n < 2)
>             return n;
> 
>         for (i = 2; i < n; i++) {
>             val = n2 + n1;
>             n2 = n1;
>             n1 = val;
>         }
>         return val;
>     }
> 
>     int main(char *argc, char **argv)
>     {
>         printf("%d\n", fib(atoi(argv[1])));
>         return 0;
>     }
> 
> This was much faster than any of the recursive versions, because it 
> doesn't have to recompute the same values over and over again.  
> 

the basic translation can be for example :

let fib n =
    let val = ref 2
    and n1  = ref 2
    and n2  = ref 1
    in
    if n < 2 then n
    else for i = 2 to n - 1 do
            val := !n1 + !n2 ;
            n2 := !n1 ;
            n1 := !val
         done ;
         !val ;;

But I prefer a recursive and efficient version like this :

let fib n =
    let rec fibaux n p q =
        if n = 0 then p
        else fibaux (n - 1) q (p + q)
    in
    fibaux n 0 1 ;;

this is a terminal recursion : try it !

-- 
Laurent Chéno                   Paris (France)
<http://pauillac.inria.fr/~cheno/>
--