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.

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.

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);
}
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.”
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.
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.”
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.”
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

Software engineering student and lover of mountains.