Fibonacci
Randy
app, or direct me to a website with that information? I've looked at many
source code examples but either they didnt work for some reason or they
were'nt console based. Thank you in advance.
Randy
Arild Fines
news:uQvA0nuCCHA.1764@tkmsftngp02...
> Oh c'mon. This is a classic recursive algorithm.
No, its a classic example of an algorithm that shouldnt be implemented
recursively.
--
Arild Fines
Eric
why you would/wouldn't use a recursive algorithm for this problem? I'm
curious to get each of your reasoning.
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...
Mike Schilling
news:eU61CF2CCHA.1548@tkmsftngp05...
> Now that we've all had our 2 cents, could I get both of you to elaborate
on
> why you would/wouldn't use a recursive algorithm for this problem? I'm
> curious to get each of your reasoning.
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.
Eric
"Mike Schilling" <mscotts...@hotmail.com> wrote in message
news:qrUK8.16151$1x3.27...@newssvr14.news.prodigy.com...
Dave Girvitz
use. In point of fact, Mike, your explanation is close, but not correct.
Let's trace the algorithm (recursive) for fib(5)
fib(5)
calls fib(4) +
fib(3)
calls fib(3) + fib(2)
fib(2) + fib(1)
calls fib(2) + fib(1) fib(1)+fib(0) fib(1) + fib(0)
1
calls fib(1) + fib(0 ) 1 1 1 1
1
calls 1 1
When the function reaches the bottom level of the tree, it the returns the
correct sums. In point of fact, it is more accurate to say that the alorithm
counts the instances of 1 at the end of each branch. Thus, the statement
that fib(5) = fib(4) + fib(3) is correct, but cannot use the information of
the value of fib(3) is technically not correct as the sum itself is not
calculated at that point.
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...
Mike Schilling
> Ahhhhh, recursion, the subject that acadmics love, but professionals never
> use. In point of fact, Mike, your explanation is close, but not correct.
> Let's trace the algorithm (recursive) for fib(5)
> fib(5)
> calls fib(4) +
> fib(3)
> calls fib(3) + fib(2)
> fib(2) + fib(1)
> calls fib(2) + fib(1) fib(1)+fib(0) fib(1) +
fib(0)
> 1
> calls fib(1) + fib(0 ) 1 1 1 1
> 1
> calls 1 1
> When the function reaches the bottom level of the tree, it the returns the
> correct sums. In point of fact, it is more accurate to say that the
alorithm
> counts the instances of 1 at the end of each branch. Thus, the statement
> that fib(5) = fib(4) + fib(3) is correct, but cannot use the information
of
> the value of fib(3) is technically not correct as the sum itself is not
> calculated at that point.
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.
Dennis Roark
> 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
Randy blah
*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!