Re: Fabonicseries Program required

Eric Sosman wrote:

fib(100000) is a 69424-bit number, and adding numbers of
that size is likely to take more than "no time."

Still, the iterative solution beats the pants off recursion.

On my machine the iterative form takes ~ 0.024 seconds for fib(10,000). The
memoised recursive form takes around 0.09 seconds.

Not really a trouser-ripping difference in speed. What matters more is that
the recursive form blows the default stack at around fib(8,000), and the
default heap somewhere before fib(40,000).

I assume that the increased GC load of the memoised version explains the
difference in speeds -- which otherwise seems implausibly great (the BigInteger
adds should /swamp/ the array accesses and null-tests).

-- chris



.

Relevant Pages

  • Re: Recursive functions
    ... point is to learn about recursion. ... *really* useful, or explicitly tell the students "This is just an example, ... both possible, 99% of times iteration is more efficient, and 90% of times ... solution is cleaner than an iterative solution, ...
    (comp.lang.c)
  • Re: Question about a solution to excercise 4-13 in K & R
    ... Write a recursive version of the function reverse, which reverses ... "This is not a good application of recursion". ... I'm sort of mystified why reversing a string in place recursively is ... space where an iterative solution wouldn't. ...
    (comp.lang.c)
  • Re: Question about a solution to excercise 4-13 in K & R
    ... Write a recursive version of the function reverse, which reverses ... "This is not a good application of recursion". ... I'm sort of mystified why reversing a string in place recursively is ... space where an iterative solution wouldn't. ...
    (comp.lang.c)
  • Re: What is the general formula for the series 1, 2, 4, 7, 11, .........
    ... after this write some members by replacing backward. ... I have never come across or forgotten what the recursive form is. ... a recursion formula involving the prior two members of ... the sequence, a la the Fibonacci sequence, is ...
    (sci.math)