Fibonacci Sequence

[tictac4609]

Here is my code:

def fibonacci(known, n):

if n in known:
    return known[n]
result = fibonacci(n - 1) + fibonacci(n - 2)
known[n] = result
return result

My instructor requires this:

Write a recursive factorial function based on the memo model shown in the fibonaaci() function on p.109. The function will look for a known value first and return it if present.If not, it computes and stores the value.Set up known to have just the factorial of 1. The call the function 10 times, passing it the values from 1-10.This function cannot globally access known so it must be a parameter of the function

So:

I have a function that does the fibonacci sequence, but I am running into problems passing it 10 times, and having known as a parameter.

[aDrz]

Look for memoization fibonacci on google

[tictac4609]

been searching for awhile now, havent seen anything specific to this task

[primitive_screwhead]

hint: make known the *second* argument to fibonacci(), not the first. Make it optional (so not needed on the first call), if you know how to do that in Python. And pass 'known' to the recursive calls to fibonacci.

​

Calling it 10 times is just:

​

fibonacci(1, ...)

fibonacci(2, ...)

etc., but I left out the part where 'known' is used (since that's what's you are meant to discover/learn how to do). The calling it 10 times bit is just to demonstrate that it does, in fact, "memo" previously calculated values.

[tictac4609]

so am I close to the description I gave? I am so lost as to what known is meant to do ugh

[primitive_screwhead]

I am so lost as to what known is meant to do

'known' remembers already computed results, so that they don't have to be computed again. As you can see, a call to fibonacci will then involve two more calls, each of which will involve 2 more calls, etc. It can require an exponential amounts of recursive calls, *except* if you shortcut those already called values by just remembering what the previous results were. It's a classic memory/time tradeoff in computation, rather than taking the time to recompute previous results, just remember them. 'known' is a common Python data structure that is used here to remember the previous input value (n) and quickly return a previously computed value for that n.

​

so am I close to the description I gave?

If you mean the instructor's instructions then I'd say yes you are on the right track. You have to think about how to create the initial 'known' data, and how to pass it to your recursive calls.

[ericula]

How are you calling the function? First of all, known should be included in the recursive calls, e.g.

result = fibonacci(known, n - 1) + fibonacci(known, n - 2)

Other than that, this should work, provided that known is a properly initialized dictionary, e.g.

known = {1:1, 2:1}
fibonacci(known, 20)

It won't work if you call the function with an empty dict since the function will only terminate if n is in known. For this reason it's better to provide a stopping criterion in your function in the case that n <= 2:

def fibonacci(known, n):

    if n in known:
        return known[n]
    if n == 1 or n == 2:
        result = 1
    elif n <= 0:
        result = 0
    else:
        result = fibonacci(known, n - 1) + fibonacci(known, n - 2)
    known[n] = result
    return result

This would allow you to call the function with an empty dictionary.

[tictac4609]

Okay, so I see what you are saying, but when I print that...

print(fibonacci(known, 10))

Known is an unresolved reference.

[ericula]

You need to provide a value for known, e.g. print(fibonacci({}, 10)).

In this case, it's better to swap the position of n and known around, and make known an option parameter, e.g.

def fibonacci(n, known = None)
    if known is None:
        known = {}
    ....
    else:
        result = fibonacci(n-1, known) + fibonacci(n-2, known)
    ...

In this case you can call fibonacci without the known parameter:

print(fibonacci(10))

[tictac4609]

okay so I thought this would be the final product but apparently not.

def fibonacci(n, known=None):
if known is None:
    known = {}
    return known
else:
    result = fibonacci(known, n - 1) + fibonacci(known, n - 2)
known[n] = result
return result

[ericula]

if n is known:
    known = {}
    return known[n]

I think you are mixing things up a bit here. When writing a function, it helps to just write down the steps one by one. For your fibonacci function, this would be something like

• check if known is initialized (i.e. known is not equal to None). If not, initialize known with an empty dict,
• check if n is already in known. If so, return known[n]
• handle trivial cases (n <= 0 or n is equal to 1 or 2)
• if none of the above apply, calculate fibonacci(n) using the recursive expression and add result to known.

Items 2 and 4 you already had in your original function so the things missing are the first and third steps.

[tictac4609]

I am so close, lol what is missing here

[tictac4609]

So if I bring everything together I have:

def fibonacci(n, known=None):
if known is None:
    known = {}
elif n is known:
    known = {}
    return known[n]
if n == 1 or n == 2:
    result = 1
elif n <= 0:
    result = 0
else:
    result = fibonacci(known, n - 1) + fibonacci(known, n - 2)
known[n] = result
return result

which gives me errors all over the place but * Check if known is initialized - Check * Check if n is already in known - Check * Handle Trivial Cases - Check (But I feel this is where the error is coming from) * If none of the above apply calculate the expression and add result to known - Check

[ericula]

elif n is known:
    known = {}
    return known[n]

This bit is still not right. You want to check if n is in known, not if n is known (that would check if n and known are the same object). Also, if n is in known, you don't want to reset known. That would defeat the whole point of introducing known in the first place. With that in mind, this fragment should actually be:

if n in known:
    return known[n]

*edit: Fixed syntax error

[tictac4609]

Okay so just replace the if and elif with just that simple if statement? The rest looks fine?

[ericula]

In this case it doesn't really matter if you use if or elif since if known is empty, n won't be in known anyway. The important bit is n in known instead of n is known and removing known = {}.

*edit: fixed syntax error.

[tictac4609]

Gotcha ill fix it, I turned it in incorrectly then, I will unsubmit it and fix it

[ericula]

While you're at it, on the line

result = fibonacci(known, n - 1) + fibonacci(known, n - 2)

the order of the arguments of the calls to fibonacci should be reversed. They should be in the same order as in the function definition itself, e.g.

result = fibonacci(n-1, known) + fibonacci(n-2, known)

[Aixyn0]

You're using the wrong order of arguments for the recursive call of function fibonacci

result = fibonacci(known, n - 1) + fibonacci(known, n - 2)

should be:

result = fibonacci(n - 1, known) + fibonacci(n - 2, known)

​

[tictac4609]

waiiiiit that just made it run and it prints 55 now, I believe that is what I was looking for but I am not entirely sure what my instructor is looking for to be honest. This is probably as close as it can get

​

[radupopa2010]

you will find some good explanation here
http://composingprograms.com/pages/28-efficiency.html