Recursion

A recursive function solves a problem by solving a smaller version of the same problem and combining. It needs a base case, an input small enough to answer directly, or it calls itself forever: factorial(0) is 1; factorial(n) is n * factorial(n - 1).

Recursion fits problems that are naturally nested, like a list that contains lists. To flatten one, walk the items: a plain item goes into the result, a list gets flattened recursively and its items go in. Python limits the depth to about a thousand calls, so recursion is for structure, not for counting to a million.

def count_down(n):
    if n == 0:
        return []
    return [n] + count_down(n - 1)

print(count_down(3))   # [3, 2, 1]

Your task

Write factorial(n), fib(n) returning the nth Fibonacci number with fib(0) = 0 and fib(1) = 1, and flatten(nested) that turns a list containing lists (to any depth) into one flat list.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)


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


def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result