No, its a classic example of an algorithm that shouldnt be implemented
recursively.
--
Arild Fines
I didn't because I wanted the code to be as easy to read as possible, given
that I thought his problem was with writing a console app, not with a
formula to calculate fibonacci numbers. I assumed (maybe incorrectly) that
anyone that knew the term would know how to calculate them.
"Arild Fines" <arild...@should.not.be.here.broadpark.no> wrote in message
news:ON#DsRxCCHA.1724@tkmsftngp02...
It's a classic problem that you shouldn't solve with recursion. Think about
what a recursive algorithm would look like:
int fib(int num)
{
if (fib <= 1)
return 1;
else
return fib(num-2) + fib(num-1);
}
When fib(num-2) returns, it's done all the work to calculate fib(num-1)
except for one more addition. But fib(num-1) has no idea of that; it uses
none of that information and restarts the calculation from scratch. The
result is that adding 1 to num makes the calculation about twice as
expensive. Think about the number of additions done in the recursive and
iterative algorithms:
num 2 3 4 5 6 7
8 9
1+1, iterative 1 2 3 4 5 6
7 8
1+1, recursive 1 2 4 7 12 20 33
54
Where the iterative algorithm is linear in num, the recursive one is
exponential.
"Mike Schilling" <mscotts...@hotmail.com> wrote in message
news:qrUK8.16151$1x3.27...@newssvr14.news.prodigy.com...
What recursive algorithms gain are elegance. They are very easy to read.
Their drawbacks however are:
1) They are slower than linear functions (function calls require more
operations than simple adds).
2) They are memory hogs. In this case, 15 addresses in memory have to be
stored where a linear function would only require 3 or 4. In older languages
that store all variables in the stack (Pascal, C. etc.) , this would often
lead to stack overflow errors (around fib(20) if I remember correctly). This
is harder to do in C# becuase classes are stored on the heap, thus giving
access to a larger amount of memory. I haven't tried it, but if you change
the class I sent to a struct (that is stored on the stack), I think you
would also encounter this problem.
Hope this helps. By the way, I am enjoying this.
Dave
"Eric" <removeth...@itsg.iconixx.com> wrote in message
news:uyAJqN3CCHA.1436@tkmsftngp04...
I don't understand the point you're trying to make.
In the recursive implementation, fib(5) calls fib(4) and fib(3). fib(4)
also calls fib(3). The inefficiency of the algorithm stems from the fact
that the same calculation is done more than once. In fact, there's a pretty
familiar pattern in the number of times fib(n) is called in calculating,
say, fib(6):
fib(6) 1
fib(5) 1
fib(4) 2
fib(3) 3
fib(2) 5
fib(1) 8
The iterative algorithm, on the other hand, calculates fib(n) exactly once
for each n.
> In the recursive implementation, fib(5) calls fib(4) and fib(3).
> fib(4) also calls fib(3). The inefficiency of the algorithm stems
> from the fact that the same calculation is done more than once. In
> fact, there's a pretty familiar pattern in the number of times fib(n)
> is called in calculating, say, fib(6):
>
> fib(6) 1
> fib(5) 1
> fib(4) 2
> fib(3) 3
> fib(2) 5
> fib(1) 8
>
> The iterative algorithm, on the other hand, calculates fib(n) exactly
> once for each n.
>
>
>
As others have said, recursion would be a horrible way to calculuate the
Fibonacci series. In terms of Big Oh notation, the recursive version is
2 raised to the n, the iterative version will be on the order n. The
difference is great. The classic Towers of Hanoi may be a good
recursive algorithm that is order 2 exp(n) but only because an iterative
version is not obvious (as it is with Fib. sequence) and one uses TOH as
a demonstration, not for practical work. I have my students compare the
time for recursive and non-recursive versions of the Fibo sequence
precisely to show that finding the order of an algorithm is important
and that recursion may look simpler but be far too costly.
--
Dennis Roark
de...@earthlink.net
Starting Points:
www.home.earthlink.net/~denro
*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!