Fibonacci Problem Help!!

[babutche]

HI,

I HAVE BEEN TRYING TO FIGURE THIS PROBLEM OUT ALL DAY LONG. CAN SOMEONE PLEASE HELP ME ALONG? I WILL TELL YOU THE PROBLEM AND THEN SHOW YOU WHAT I HAVE SO FAR. I AM TRYING TO MODIFY THIS RECURSIVE PROGRAM:

def fib(n):
if n < 3:
return 1
else:
return fib(n-1) + fib(n-2)

I NEED TO MODIFY THE PROGRAM BY HAVING IT PRINT TRACING INFORMATION. IN OTHER WORDS THE OUTPUT SHOULD LOOK SOMETHING LIKE THIS:

Computing fib(4)
...
Leaving fib(4) returning 3

THIS IS WHAT I HAVE COME UP WITH SO FAR: (I AM NEW AT THIS SO BEAR WITH ME, PLEASE)

def fib(n):
if n < 3:
return 1
while n > 3:
x = n-1
y = n-2
print "Computing fib", n
print x,y
print fib(n-1)+fib(n-2)
print "Leaving fib", n 
print "Return", y
return fib(n-1) + fib(n-2)
 
def main():
n = input("Enter: ")
fib(n)

I CAN UNDERSTAND HOW THE FIBONACCI NUMBERS WORK BUT I AM STUCK RIGHT NOW. I HAVE GOTTEN MY PROGRAM TO RUN SEVERAL DIFFERENT WAYS BUT NOT THE PROPER WAY. CAN ANYONE HELP ME WITH THIS PROGRAM AND EXPLAIN.

THANK YOU!

[jrcagle]

HI,

I NEED TO MODIFY THE PROGRAM BY HAVING IT PRINT TRACING INFORMATION. IN OTHER WORDS THE OUTPUT SHOULD LOOK SOMETHING LIKE THIS:

Computing fib(4)
...
Leaving fib(4) returning 3

THIS IS WHAT I HAVE COME UP WITH SO FAR: (I AM NEW AT THIS SO BEAR WITH ME, PLEASE)

    def fib(n):
    if n < 3:
    return 1
    while n > 3:
    x = n-1
    y = n-2
    print "Computing fib", n
    print x,y
    print fib(n-1)+fib(n-2)
    print "Leaving fib", n 
    print "Return", y
    return fib(n-1) + fib(n-2)

    def main():
    n = input("Enter: ")
    fib(n) 

I CAN UNDERSTAND HOW THE FIBONACCI NUMBERS WORK BUT I AM STUCK RIGHT NOW. I HAVE GOTTEN MY PROGRAM TO RUN SEVERAL DIFFERENT > WAYS BUT NOT THE PROPER WAY. CAN ANYONE HELP ME WITH THIS PROGRAM AND EXPLAIN.

THANK YOU!

You have a good beginning here, I think. Here are a couple of things to consider:

(1) Style: use code-tag rather than inline-code for your posts, because it shows syntax more clearly. Also, don't forget to indent your blocks!

(2) Why use 'while' in line 4? while is supposed to create a loop; but at the end of the while block, you return a value, so you aren't intending to loop. Rather than 'while', an 'elif' would be appropriate. Which leads to ...

(3) What happens if n == 3 exactly? That's where your error message is coming from.

I hope this helps, and once you get it working, post your success!

Jeff