Eric Sosman <(E-Mail Removed)> wrote:

> <rant topicality="zero">

>

> Why do people so often talk about factorials or the

> Fibonacci numbers when explaining recursion? Neither is well-

> suited to a recursive solution; iteration wins on practically

> every measure.
Not necessarily so. The following is a re-expression of the fibonacci

sequence recursive formula:

f[0] = 0

f[1] = 1

f[2] = 1

f[n] = f[(n+1)/2]^2 + f[(n-1)/2]^2 ; if n is odd

= f[n/2+1]^2 - f[n/2-1]^2 ; if n is even

Which implies a recursion of depth about ln(n) steps. Now if you do

the math, you will realize that the total number of calls does in fact

lead to O(n) which might lead you to believe that iterative is faster

(since its less complicated). However, if you cache the values as you

compute them, then this should run in about O((ln(n))^2) which should

*SKUNK* the iterative solution for large enough n.

> [...] And for the Fibonacci numbers, iteration itself

> is easily beatable;
By a complete table look up of course! (No this will not blow out your

memory; think about it.)

> [...] recursion is at best a poor third choice.
As I pointed out above, depends on which recursive formula you are

talking about.

> But look up any textbook or lecture about recursion, and what

> do you find? Factorials and Fibonacci! Foolishness!
They are the easiest examples -- they can't explain trees until they

explain recursion.

--

Paul Hsieh

http://www.pobox.com/~qed/
http://bstring.sf.net/