A crochet needle is looped into a gray and white project. White and gray bundles of yarn sit attached to the project.
Photo by Kelly Sikkema on Unsplash

A (mostly) stress-free guide to recursion

Remember in elementary school how there was always that one topic that the kids in the grade above would warn you about? They’d whisper horror stories about learning multiplication or cursive (am I aging myself here?) at the bus stop, sending a chill into the students in the grades below.

Recursion is that topic for many programmers. It comes in whispers and horror stories. But the thing is, just like cursive and multiplication, it becomes much easier with practice. Don’t get me wrong — I still have to practice explaining it out loud in order to understand what I’m doing. But hey, we all did multiplication on our fingers at one point.

What is recursion?

A recursive function is one that calls itself. It’s often shown as nesting dolls or a picture of a picture of a picture.

I like to think of recursion as crochet. You loop into the same yarn over and over until you hit a case where it’s no longer necessary.

But how does it work?

Let’s take a look at a practice case:

float _pow_recursion(float x, float y)
{
if (y == 0)
return (1);
if (y < 0)
return (_pow_recursion(x, y + 1) / x);

return (_pow_recursion(x, y - 1) * x);
}

This recursive function multiplies x to the power of y.

An arrow from the first row of _pow_recursion points to a box that reads “recursive function.” Another arrow points from “if y == 0 then return 1” to a box that says “base case.” Another arrow points from the final two lines to a box that reads “recursive call.”
An arrow from the first row of _pow_recursion points to a box that reads “recursive function.” Another arrow points from “if y == 0 then return 1” to a box that says “base case.” Another arrow points from the final two lines to a box that reads “recursive call.”

Whenever the function hits one of the recursive calls, it will reenter the recursive function. This loop will continue until it reaches the base case where y == 0.

A map reads: Does y == 0? If yes, return 1. If no, then is y less than 0? If yes, reenter the recursive function with x and y + 1, then divide the result by x. If no, then reenter the recursive function with x and y — 1, then multiply the result by x.
A map reads: Does y == 0? If yes, return 1. If no, then is y less than 0? If yes, reenter the recursive function with x and y + 1, then divide the result by x. If no, then reenter the recursive function with x and y — 1, then multiply the result by x.

Each time the function goes through the recursive loop, it adds to the stack. A stack is first in, first out, meaning that the first set of values is pushed to the bottom of the stack. All items are popped from the top of the stack.

A series of boxes are stacked on top of each other. An arrow points to the bottom box, labeled “first in, last out.” A different arrow points from the top box to the outside of the image, labeled “last in, first out.”
A series of boxes are stacked on top of each other. An arrow points to the bottom box, labeled “first in, last out.” A different arrow points from the top box to the outside of the image, labeled “last in, first out.”

Now that we have the pieces together, let’s try to walk through a real example with x = 3 and y = 3.

A map reads: Does y == 0? If yes, return 1. A highlighted portion says, “If no, then is y less than 0?” If yes, reenter the recursive function with x and y + 1, then divide the result by x. A highlighted portion says, “If no, then reenter the recursive function with x and y — 1, then multiply the result by x.”
A map reads: Does y == 0? If yes, return 1. A highlighted portion says, “If no, then is y less than 0?” If yes, reenter the recursive function with x and y + 1, then divide the result by x. A highlighted portion says, “If no, then reenter the recursive function with x and y — 1, then multiply the result by x.”

When we go through the loop, we end up building the following stack:

A series of boxes are stacked on top of each other. From bottom-to-top, they read, pow(3, 3) * 3, which corresponds with 9 x 3 = 27. Below it, pow(3, 2) * 3 corresponds with 3 x 3 = 9. Next, pow(3, 1) * 3 corresponds with 1 x 3 = 3. Finally, Base Case x = 3 and y = 0 returns 1. Next to this there are a series of equations. From top-to-bottom, they read
A series of boxes are stacked on top of each other. From bottom-to-top, they read, pow(3, 3) * 3, which corresponds with 9 x 3 = 27. Below it, pow(3, 2) * 3 corresponds with 3 x 3 = 9. Next, pow(3, 1) * 3 corresponds with 1 x 3 = 3. Finally, Base Case x = 3 and y = 0 returns 1. Next to this there are a series of equations. From top-to-bottom, they read

As you can see, we end with the answer that 2 to the power of 2 is 4.

Now take another breath. You’ve got this.

Software engineering student and lover of mountains.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store