fibonacci series what Iam is missing ?

[Dave Angel]

On 03/23/2015 12:16 PM, Chris Angelico wrote:
> On Tue, Mar 24, 2015 at 3:01 AM, Ganesh Pal <ganesh1pal at gmail.com> wrote:
>> Hello team ,
>>
>>
>> [root at localhost Python]# cat  fibonacci-Sequence-3.py
>>
>> ## Example 2: Using recursion
>> def fib(n):
>>      if n == 0:
>>          return 0
>>      elif n == 1:
>>          return 1
>>      else:
>>          return fib(n-1) + fib(n-2)
>> print fib(5)
>>
>> # python  fibonacci-Sequence-3.py
>> 5
>>
>> what Iam I missing in the program , I was expecting 0,1,1,2,3 ?
>
> What you're doing is printing out the fifth Fibonacci number. So there
> are three things to note:
>
> 1) To display the entire sequence, you will need some sort of loop.
> 2) Your algorithm is about as hopelessly inefficient as it could
> possibly be, barring deliberate intent. [1]
> 3) You are running Python 2.x; unless you have a good reason not to,
> it's better to use Python 3.
> 4) You're running as root. Normally, something like this should be run
> as a regular user - it's safer that way.
>
> Err, *amongst* the things to note are such diverse elements as...
> etcetera, etcetera. Ahem.
>
> I would suggest rewriting this as a much more straight-forward loop;
> begin at the beginning, go on till you reach the point you wanted,
> then stop.
>
> ChrisA
>
> [1] Cue the demonstration of a worse version from someone's student?
>

I'll give you a worse version.  Back in the day I had occasion to write 
a simple program in a language which had no add or subtract.  It could 
only increment and decrement indices.  So to simulate that:


#without using any arithmetic other than increment and decrement
def fib3(n):
     if n == 0:
         return 0
     elif n == 1:
         return 1
     else:
         a = fib3(n-1)
         n = n-1
         b = fib3(n-1)
         while b > 0: a,b = a+1, b-1
         return a

Interestingly enough that only seems to triple the time taken.

I wouldn't recommend running either of these with n > 34 or so.

## Example 2: Using recursion with caching
cache = [0, 1]
def fib4(n):
     if len(cache) <= n:
         value = fib4(n-2) + fib4(n-1)
         cache.append(value)
     return cache[n]

This one takes less than a millisecond up to n=200 or so.

-- 
DaveA