Recursion

Recursion is when a function calls on itself to complete. Recursive functions are made up of two parts: a base case and a recursive call. Let’s look at factorials. 4! is simply 4*3*2*1 = 24. We can write this iteratively with a for loop:

answer = 1
factorial = 4

while factorial > 1:
    answer = answer * factorial
    factorial -= 1

# 4! = 4*3*2*1 = 24

A recursive function breaks a problem into a smaller problem. We can rewrite 4! as 4*3!. We can then write 3! as 3*2!. We would repeat this until we get to 1! which is our base case. The base case ensures that our recursive function does not loop forever. The time complexity is O(n) time. Here is what the code looks like:

def factorial(x):
    # Base case
    if x <= 1:
        return 1

    return n * factorial(x - 1)

We can also have two branches of recursion. Take Fibonacci numbers as an example. We can define the function as f(x) = f(x-1)+f(x-2). The base case would be F(1) = 1 and F(0) = 0. Our code would look like:

def fibonacci(x):
    if x <= 1:
        return x

    return fibonacci(x - 1) + fibonacci(x - 2)