15 Recursion And Memoization - Notebook by Amgad Hussein (amgd2112)

Learn practical skills, build real-world projects, and advance your career

Created 4 years ago

Recusive and Fibonacci

$fib(n) = fib(n - 1) + fib(n - 2)$

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

%%time
fib(30)

CPU times: user 238 ms, sys: 3.59 ms, total: 241 ms
Wall time: 240 ms

%%time
#
# can't execute with a large number, because it takes too long.
#
fib(40)

CPU times: user 29.3 s, sys: 7.7 ms, total: 29.3 s
Wall time: 29.3 s

102334155