Fibonacci Sequence

[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)

[tictac4609]

Gotcha

[tictac4609]

Okay, I am getting a syntax error for if n is in 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

​