Newbie Help

[babutche]

Hi,

I am trying to figure out how to print tracing information for Fibonacci numbers.

output =

Computing fib(4)

Leaving fib(4) returning 3

Can anyone steer me in the right direction?

This is what I have:

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

My output is looking like this:

>>> 
>>> fib(4)
Computing fib 4
fib 3 + fib 2
Leaving fib 4
Return Computing fib 3
fib 2 + fib 1
Leaving fib 3
Return 2
3
Computing fib 3
fib 2 + fib 1
Leaving fib 3
Return 2
3
>>>

I cannot get my return of the Fibonacci number to work properly and when I ran this program with fib(10) it ran forever.

:mrgreen: Thanks!

[woooee]

I cannot get my return of the Fibonacci number to work properly and when I ran this program with fib(10) it ran forever.

'Ran forever' because you are calculating using the same number over and over. Look at your output. If you want to compute a fib you first have to start with two numbers. The sequence 1, 1, 2, 3, 5 actually starts with zero and one. You can start with any two numbers you want, or with one number and number-1, so if we start with 10 and 10-1=9, store those two numbers in a list, pass the list to the function which adds them together, then element[0] = element[1], and element[1] = the sum, and continue by returning the updated list. If you still can't figure it out, post back. When testing a loop, it is a good idea to put in a counter and if it is greater than some number, say 1000, exit with an error message.

Edit: I'm now wondering if you want to calculate the fibs used to calculate a number. I would think that mpossible as it can be any two numbers in combination. For example 10=9+1 or 8+2, etc. If you can explain what you want to do in words or have some math, please post back.

[babutche]

Hi,

See post below please. Sorry I forgot code tags.

[babutche]

Hi,

It is suppose to show each time the recursion is called and returned in the recursive program. I really don't understand it myself because I am having a hard time understanding recursion. If anyone can explain how recursion works I would greatly appreciate it. I have read about it but it just looks like a loop to me. I am not very good at this. I am just a beginner. Sorry.

Anyway I have changed my program around but I still cannot get it to print tracing information. this is what I have:

import math
def fib(n):
    a,b = 0,1
    while b < n:
        print b,
        print "Computing fib: ", n
        a, b = b, a+b
        print  a, b
        print "Leaving fib", n

I am stuck! I don't understand.

[woooee]

Recursion usually means something that calls itself. The following is a link to a sort that uses recursion. Note that in the sort there is a way to tell if the item has already been tested/done. Recursion is used for things like sorts and walking a directory to get files from subdirectories.
http://www.faqts.com/knowledge_base/view.phtml/aid/4491

##Recursion to compute a factorial
def factorial(n) :
   if n < 2 :
      return 1
   else :
      return ( n * factorial(n-1) )

[vegaseat]

A function calling itself, or recursion, is like a loop. As with any loop you have to give it an exit condition, or it will keep going. So, watch out that your test print statements don't ruin your exit condition or call the function itself.

Just out of curiosity I put in the only test print statement I could think of into the standard recursive Fibonacci Number function. Since the function calls itself twice each time around, it makes for a surprising number of time expensive function calls, and is as inefficient as the government!

def fib(n):
    print "Doing fib(%d)" % n  # test!!!
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

print fib(10)

For fib(30) the recursive function is 75,000 times slower than the usual nonrecursive function ...

def fib(n):
    (current, previous) = (0, 1)
    while n > 0:
        (current, previous) = (previous, current + previous)
        n -= 1
    return current

[babutche]

I can get this to print out the fib #. But I don't know how to print out each call/return. Maybe you can guide me in the right direction. Even though this problem has caused me some grief it, has been fun to mess with. But I want to get it to run properly.

Here is what I am figuring:

Let's take fib(7)

fib(7) = 13 = 8 + 5 (curr/ prev)

fib(6) = 8 = 5 + 3 (curr/ prev)

fib(5) = 5 = 3 + 2 (curr/ prev )

2 + 3 = 5 is now curr + prev = curr(fib(6) curr)

2 = 2 is now fib(4)curr = fib(5)prev

fib(4) = 3 = 2 + 1 (curr/ prev)

fib(3) = 2 = 1 + 1 (curr/ prev)

I am realizing I need to store some things here but I'm not sure what or how, right now.
1 1 2 3 5 8 13

To call fib(7):
fib(7)
fib(6) fib(5)
fib(7-1) fib(7-2)
fib(5) fib(4) fib(4) fib(3)
fib(6-1) fib(6-2) fib(5-1) fib((5-2)

and so on.........
n = 7
but each time around n must decrease by 1. Right?
Then n is equal to the next fib.
So I need an accumulator?

The outside functions on the far left hand side = n-1 each time around the loop
The inside function on the far L.H. side = n-2 each time around loop
Right hand side is :
inside function = n-1
outside function = n-2

Well, I just got lost maybe you can help! Thanks!!!

[woooee]

Let's take fib(7)

fib(7) = 13 = 8 + 5 (curr/ prev)

fib(6) = 8 = 5 + 3 (curr/ prev)

fib(5) = 5 = 3 + 2 (curr/ prev )
I am realizing I need to store some things here but I'm not sure what or how, right now.
1 1 2 3 5 8 13

Perhaps append a fib sequence to a list until the value is greater than the input number? That should give you the info. If you want to use recursion, you can use it to calculate the fib list. Personally, I would use a while loop, but whatever.

[woooee]

The outside functions on the far left hand side = n-1 each time around the loop
The inside function on the far L.H. side = n-2 each time around loop

If n=list element >= input number, then n-1 and n-2 = element numbers that make up the fib, or am I also confused?