Recursion Basics

Recursion is a method where a function calls itself to solve smaller instances of the same problem. It is particularly useful for divide and conquer problems; however, it can be difficult to understand exactly what is happening, since each recursive call is itself spinning off other recursive calls.

Every recursive function must have two parts:

1. Base case – a condition where the recursion stops. Without one, a recursive call lasts forever until a stack overflow/segfault occurs.
2. Recursive case – the part where the function calls itself with a smaller or simpler input.

Understanding recursion comes down to recognizing how each call reduces the problem and how the base case eventually stops the chain of calls. A simple problem that naturally lends itself to a recursive solution is calculating factorials. The recursive factorial algorithm defines two cases: the base case when n is zero, and the recursive case when n is greater than zero.

def factorial(n):
    #test for a base case
    if n == 0:
        return 1
    else:
        # make a calculation and a recursive call
        f = n * factorial(n - 1)
        print(f) #print intermediate results (optional)
        return (f)

How Recursion Works

Let’s say we are tasked to print a number from 1 to n using recursion. Below is how the code would look like:

def more(n):
    if n < 1: # base case
        return
    more(n - 1)
    print(n)

more(3)

First of all, note how we check if n < 1 and then we return / exit execution of the function. This is called a base case. Normally, a recursion call lasts forever until a stack overflow/segfault occurs. In order to prevent this, we add a base case to terminate the recursive calls. Now the above function prints “1, 2, 3”.

When we call the function more(3):

1. We check if the base case is true -> it is not since 3 > 1
2. We call the function itself with a decrement of n. This calls the same function again in the recursive tree. So the function more(3) hasn’t stopped executing.
3. We go to the 2nd function more(3 - 1), check for the base case and recall the same function in the recursive tree.
4. We keep doing that until the base case becomes true, only then do we return/break the functions executions…therefore printing n on each function exit.

This is how the recursive call looks like visually:

How to Think Recursively

When approaching a recursion problem, always follow these steps:

1. Identify the base case. What is the simplest version of the problem that can be solved directly?
2. Assume the recursive call works. Trust that your function correctly handles smaller inputs.
3. Build the current step. Use the result from the smaller problem to solve the larger one.
4. Test with small inputs. Tracing a small example (like n = 3) helps you understand how calls stack and return.

Recursion becomes easier once you realize that you are breaking a big task into smaller self-similar tasks until you hit the simplest possible one.