Exercises
Recursion
3 tasks. Write the code, press Check, and the page runs it against a real Python interpreter.
Exercise 1Passed
Write factorial recursively.
Python
def factorial(n):
# base case, then the recursive step
pass
print(factorial(5))n <= 1 returns 1; otherwise n times factorial(n - 1).
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5))Exercise 2Passed
Add up every number in the nested lists, however deep they go.
Python
def total(items):
# recurse into any nested lists
pass
print(total([1, [2, 3], [4, [5, 6]]]))isinstance(item, list) tells you when to recurse.
def total(items):
running = 0
for item in items:
if isinstance(item, list):
running += total(item)
else:
running += item
return running
print(total([1, [2, 3], [4, [5, 6]]]))Exercise 3Passed
This recomputes the same values enormously often. Cache it so fib(30) is instant.
Python
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(30))functools has a decorator that caches results by argument.
from functools import lru_cache
@lru_cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(30))