I’m currently working through the recursion chapter of Cracking the Coding Interview. Recursion is essentially using the same function repeatedly to solve smaller subsets of the initial data.

The Fibonacci numbers are a good example of this (i.e. 1, 1, 2, 3, 5, 8, 13…). Each number is the sum of the previous two numbers.

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

If we are trying to find the 4th fibonacci term, we would have to first find the 2nd and 3rd term and so on and so forth. Recursion only works if there is a base case that eventually returns something. In this example, when n is eventually 0 or 1, the value 1 will be returned.