A Beginners Guide to Recursion

Recursion: the repeated application of a recursive procedure or definition.

A recursive function is a function that calls on itself to complete a task, resulting in the function running many times until the base condition is met. Each time the function is called we make it slightly smaller which makes the task easier to complete. Recursion can be a valuable tool in your programming arsenal if used correctly! For example, let's say we wanted to write a recursive program to “eat a sandwich”. In pseudocode, our program would look like this:

1. If the sandwich does not exist; do nothing
2. Else take a bite out of the sandwich, and run “eat a sandwich”

Each time we run “eat a sandwich” we take a bite out of the sandwich (make the problem smaller), then we run it again until the sandwich is gone and we are full!

Anatomy of Recursion

Want to read this story later? Save it in Journal.

A recursive function has two basic components:

1. The base condition.
2. The recursive case.

The base condition is the simplest version of the problem and the stop point for our function. The recursive case runs an altered version of the original program until its base case has been reached.

How to Create a Recursive Function

Let’s create a function that would take an argument of a number and give us its factorial, we can call it something jazzy like “factorial”. A factorial is the product of every positive integer less than or equal to our original number and is represented with an exclamation point after the number e.g. 5! = 5x4x3x2x1 = 120

The first step is to boil the problem down incrementally. Our simplest case for a factorial function would be 1!, since 1x1 is the smallest factorial. We can also include 0! which returns 1 (Read more about that here). This will be our base case.

Next, we need our recursive case. An interesting property of a factorial is that the factorial of a number is equal to the starting number multiplied by the factorial of the number immediately below it. We can see that 5! is the same as 5x4!, and 4! is the same as 4x3!, and so on and so forth. If we multiply our original number by the function “factorial” and passing an argument or our original number minus one, we can achieve recursion!

Why Does Recursion Work

When our factorial function is called, or any function for that matter, its execution is placed on the stack. A stack is an abstract data type that works on a last-in, first-out basis(LIFO). When you add to the stack you “push” data onto it, and when you execute something from the stack you “pop” it off. A common analogy is to think of the stack as a stack of dinner plates. The last one placed on top of the stack will be the first one taken off. If we call factorial(5) our function would push its executions to the stack like this:

1. 5 x factorial(5–1)
2. 4 x factorial(4–1)
3. 3 x factorial(3–1)
4. 2 x factorial(2–1)
5. 1 => This satisfies our base case and stops our function

When it pops off the stack it will look like this:

1. 1 => 1
2. 2 x 1 => 2
3. 3 x 2 => 6
4. 4 x 6 => 24
5. 5 x 24 => 120

Now, what would happen if we removed our base case? Will our function will keep calling on factorial(num-1) until the heat death of the universe? Thankfully no! The stack has a limited amount of memory available to it, once it reaches that memory limit, your compiler will throw out a stack overflow error and stop the program in its tracks.

Summation

Recursive functions tackle large problems by boiling them down to their smallest parts. This is extremely useful when dealing with nested data structures (i.e. trees, graphs), mathematical computations, and even list sorting. If you need more information on the intricacies of recursion, this blog might shed some more light on it.

📝 Save this story in Journal.