Accueil     À propos     Téléchargement     Ressources     Contactez-nous

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

help an o'caml beginner
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2000-07-27 (21:29) From: Alain Frisch Subject: Re: help an o'caml beginner
On Wed, 26 Jul 2000, John BEPPU wrote:

> >>>
> If anyone out there could implement an O'Caml fibonacci number
> generator that doesn't make redundant calculations, I would really
> appreciate it.  I just need something to study.
> >>>

(I guess there will be many answers ..)

Here is a solution:

let fibo n =
let rec aux last x i =    (* x is u_i; last is u_{i-1} *)
if (i = n) then x
else aux x (x + last) (i + 1)
in
if (n = 0) then 1 else
aux 1 1 1

> I wrote a recursive Perl version that doesn't make redundant
> calculations, and I'd be interested to see how different in
> structure an O'Caml version would be.
>
>     sub fib_pair {
>         my \$n = shift;
>         my @seq;
>         if (\$n < 2) {
>             @seq = (1, 1);
>         } else {
>             @seq = fib_pair(\$n - 1);
>             @seq = (\$seq[1], \$seq[0] + \$seq[1]);
>         }
>         return @seq;
>     }

Well, this function is not tail-recursive (the recursive call
can't be implemented as a jump). I didn't try it, but I am pretty sure
the OCaml version will be more efficient.

--
Alain Frisch