The fibonnacci sequence is defined as below :
$$ \Large f_n = \begin{cases}n \text{ if } \leq 1\\ f_{n-1} + f_{n-2} \text{ if } n > 1 \end{cases} $$For example, the first eight Fibonnacci numbers are:
0,1,1,2,3,5,8,13 . . .
Write a recursive function fib(n)
that takes an integer n
and returns $f_n$.
def fib(n):
pass
Add print("Calculating fib of " + str(n))
at the beginning of your function (make it the first line), run it, and run the cell below :
fib(7)
How many times does it calculate fib of 1
?
# Answer here
def check_test(actual, expected):
if expected != actual:
print(f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
check_test(fib(7), 13)
check_test(fib(0), 0)
check_test(fib(1), 1)
--------------------------------------------------------------------------- NameError Traceback (most recent call last) <ipython-input-3-2b7e25bc2f6b> in <module>() 7 8 ----> 9 check_test(fib(7), 13) 10 check_test(fib(0), 0) 11 check_test(fib(1), 1) NameError: name 'fib' is not defined
We are going to store things we have computed before in a list mem
such that
$$
mem[i] = \begin{cases}-1 \text{ if we haven't computed fib(i) before }\\
f_i \text{ if we have already computed it}
\end{cases}
$$
Write a function create_memory(n)
that takes an integer n
and returns a list L of length n
that contains the integer -1
repeated n
times.
def create_memory(n):
pass
Write a function check(i, mem)
that takes an index i
and a list mem
and returns True
if mem[i]
is not equal to -1
:
def check(i, mem):
pass
Write a function add(mem, i, value)
that takes a list mem
, an index i
and an integer value
and that stores the integer value
in the list mem
at index i
:
def add(mem, i, value):
pass
Write a recursive function memo_fib(n, mem)
that takes an integer n
and a list mem
and returns $f_n$.
Here is how it should work :
def memo_fib(n, mem):
pass
Write a function fib(n)
that takes an integer n
and returns $f_n$. It should use create_memory(n)
and memo_fib(n, mem)
.
Hint: Remember that we are storing fibs from 0 to n
def fib(n):
pass
check_test(fib(7), 13)
check_test(fib(0), 0)
check_test(fib(1), 1)
Function should return the value 13, it is returning the value None Function should return the value 0, it is returning the value None Function should return the value 1, it is returning the value None