No history yet

Recursion Basics

What is Recursion?

Imagine you have a set of Russian nesting dolls. You open the largest doll to find a slightly smaller, identical doll inside. You open that one, and another appears. You keep doing this until you reach the smallest, solid doll that can't be opened. This process is a lot like recursion.

recursion

noun

A method of solving a problem where a function calls itself one or more times in its own body.

In programming, recursion breaks a large problem into smaller, more manageable versions of the same problem. Each time the function calls itself, it's trying to solve one of these smaller pieces. This continues until it hits a problem so small it can be solved directly, without calling itself again. This final, solvable piece is called the base case.

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function.

The Two Key Parts

Every recursive function needs two essential components to work correctly. Without them, it would be like opening nesting dolls forever, which is impossible.

  1. The Base Case: This is the condition that stops the recursion. It's the smallest version of the problem, the one the function can solve without calling itself. In our nesting doll analogy, it's the tiny, solid doll at the center.

  2. The Recursive Case: This is where the function calls itself, but with a modified input that brings it one step closer to the base case. It's the act of opening a doll to find a smaller one inside.

A recursive function must have a base case to prevent an infinite loop of self-calls, which would lead to a 'stack overflow' error.

Let's see this in action with a classic example: a function to count down from a number to zero. The base case is when the number is zero. The recursive case is when the number is greater than zero, where we print the number and then call the function again with the number minus one.

def countdown(n):
    # Base Case: Stop when n is 0 or less
    if n <= 0:
        print("Blastoff!")
        return
    
    # Recursive Step: Print current number and call itself with n-1
    print(n)
    countdown(n - 1)

# Let's try it out
countdown(3)

When you run countdown(3), the output will be:

3 2 1 Blastoff!

Each call to countdown reduces the problem size (n gets smaller) until it hits the base case (n <= 0).

How It Works Under the Hood

When a function calls itself, how does the computer keep track of everything? It uses something called a "call stack." Think of it as a stack of plates. Every time a function is called, a new plate is added to the top of the stack. This plate holds all the information for that specific call, like its local variables.

When a function finishes, its plate is removed from the top, and the program returns to the function represented by the plate below it.

For countdown(3):

  1. countdown(3) is called. It's not the base case, so it prints 3 and calls countdown(2). A plate for countdown(3) is on the stack.
  2. countdown(2) is called. It prints 2 and calls countdown(1). A new plate for countdown(2) is added on top.
  3. countdown(1) is called. It prints 1 and calls countdown(0). The countdown(1) plate goes on top.
  4. countdown(0) is called. This is the base case! It prints "Blastoff!" and returns. Its plate is removed from the stack.
  5. Control returns to countdown(1). It has nothing left to do, so it finishes and its plate is removed.
  6. This continues until all plates are gone and the program ends.

Ready to test your understanding? Let's try a few questions.

Quiz Questions 1/6

What are the two essential components of every recursive function?

Quiz Questions 2/6

In the Russian nesting doll analogy, what does the smallest, solid doll represent?

Recursion is a powerful concept for solving problems that can be broken down into smaller, similar sub-problems. Mastering the base case and recursive case is the key to using it effectively.