On Wed, 14 Sep 2005 14:32:17 +0200, Jerzy Karczmarczuk wrote: > First of all, the recursive version of Fibonacci IS EXPONENTIAL in complexity, > don't say such not-quite-truth as "not quite".
Your correction is noted. I had compared the work done with 2**n, but of course any constant greater than one can exhibit exponential growth. Out of interest, the number of recursive calls (including the first function call) made when calculating the nth Fibonacci number are themselves part of a Fibonacci-like sequence. Look at the 1st order differences: n Fib(n) Calls 1st Diff 0: 0 1 N/A 1: 1 1 0 2: 1 3 2 3: 2 5 2 4: 3 9 4 5: 5 15 6 6: 8 25 10 7: 13 41 16 8: 21 67 26 9: 34 109 42 10: 55 177 68 11: 89 287 110 12: 144 465 178 Notice the pattern? > But, what is more important: > > If you don't know too much about the way the functional programming is > used nowadays, please refrain from giving nonsensical examples, since > NOBODY serious programs something in the style of your recursive version. I never said that my recursive version was a practical implementation. But it is a very common algorithm -- I have four or five textbooks at home that give it. In many textbooks and programming courses, the first algorithm given to introduce the principle of recursion is either factorial or the Fibonacci sequence. For example: http://www.math.pitt.edu/~wjl/nm99.html gives the same naive recursive implementation in Fortran. If you google for Fibonacci sequences, you will find dozens, possibly hundreds, of implementations virtually identical to the one I gave. Also significant numbers of Java apps that run slow for values of n larger than 30 or 40 -- a good sign that they are using the naive algorithm. It is a rare under-graduate or secondary school textbook that suggests that the naive algorithm is anything but a poor idea. > Such anti-advertizing of recursion says less about the recursion > than about yourself. Yeah, whatever. > Here you are a recursive version linear in n; it > returns the two last Fibonacci numbers of the sequence > > def fibo(n): > if n<2: > return (n-1,n) > else: > (a,b)=fibo(n-1) > return (b,a+b) Ah, I like this algorithm! I'll add it to my collection. Thank you. -- Steven. -- http://mail.python.org/mailman/listinfo/python-list
