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

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20000727 (21:29) 
From:  Alain Frisch <frisch@c...> 
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_{i1} *) 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 tailrecursive (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