On 03/23/2015 12:16 PM, Chris Angelico wrote:
On Tue, Mar 24, 2015 at 3:01 AM, Ganesh Pal <ganesh1...@gmail.com> wrote:
Hello team ,
[root@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
--
https://mail.python.org/mailman/listinfo/python-list
