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

3 min readFeb 15, 2021

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.”

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.

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.