Your favorite video game, Mirror Maze Insanity, just released a new expansion pack (now with 20% more mirrors and a higher reflectivity ratio, whatever that means). Of course the first thing you do is race home and rip off the packaging.

As your avatar walks through the mazes, you start noticing just how many reflections there are. Each reflection's a little smaller, but it reflects in all the other mirrors, creating reflections of reflections of reflections.

Which one is even you? Are we all just reflections of larger people stuck in a mirror maze?

Okay, maybe it's time to put down the game controller. To take your mind off it, you make dinner: pancakes and cauliflower.

A classic combination.

You start cutting the cauliflower, but you notice each cut makes a smaller version of the same thing. Just like in the maze. Even worse: the pancake syrup bottle is shaped like a person holding a pancake syrup bottle.

It's time to face the music.

[cue horror movie music]

Recursion's following you.

Recursion breaks an object or thing down into smaller, identical copies. We know what you're thinking: at some point we won't be able to break the object anymore. Keep cutting that cauliflower, and you'd eventually up with a pulpy mess.

That's what we need to hit when we think recursively.

To make recursion work, we need

1. a base case (nameless white goop).
2. a starting point (a whole cauliflower).
3. rules that help us go from the starting point to the base case (the cuts that make mini-cauliflowers).

If a loop was recursive

• the base case equals the end condition.
• the start point equals the initialization. 
• the rules equal both the statements inside the loop and the incrementing of the variable.

Now before you go changing all your loops into recursive calls, stop to think about whether you actually need recursion. Why? In recursion we need to be much more careful of what rules we're using.

If we aren't, our algorithm could run infinitely. There might be some pros to running an algorithm infinitely, but we haven't found them yet. And trust us, we've tried.

RIP first laptop.

Unlike a for loop, you don't know how many steps our program will take before it reaches the end. You have to make a leap of faith and say, "With these steps, I'll eventually reach the base case."

Sometimes that leap of faith is blind. That's bad. Very bad.

Hey look, it's the basic set up of a recursive algorithm in pseudocode.

RECUR(n):
	IF n equals base case:
		RETURN value
		END IF
	ELSE:
		DO step towards base case on n
		RECUR(n-1)

Okay, that's all well and good, but let's look at a real-life example of recursion in action.

The Fibonacci Sequence

The Fibonacci Sequence, which models a ridiculous amount of natural patterns , defines the value of n completely on the last value of n added to the value of n before the last value. In math terms, that looks like this:

Fib(n) = Fib(n – 1) + Fib(n – 2)

But wait! If we leave the algorithm like this, it'll keep trying to find n-1 and n-2 infinitely without ever giving n a value. (Hence the term, "infinite recursion.")

We need to specify a base case so that the function doesn't keep going infinitely. Our base cases (two in this algorithm: one for n – 1, and the other for n – 2), look like this:

Fib(0) = 0
Fib(1) = 1

This now means that the Fib() definition we had before no longer holds true for every value of n, so we need to change the definition:

Fib(n) = Fib(n – 1) + Fib(n – 2), n > 1

Fib(0) = 0
Fib(1) = 1

If n = 0, Fib(n) is 0; if n = 1, Fib(n) is 1. These two cases tell us when to stop subtracting fromn so that we don't spiral into recursive madness.

If n = 5:

Fib(5) = Fib(4) + Fib(3)

That's all well and good, but there's one problem: we have no idea what Fib(4) or Fib(3) are. We need to solve those before finding Fib(5).

Fib(4) = Fib(3) + Fib(2)
Fib(3) = Fib(2) + Fib(1)

We know what Fib(1) is, but we still don't know what Fib(2) is.

Fib(2) = Fib(1) + Fib(0)

Eureka! We're hit the base cases. Now we can stop drilling down and start solving the problem.

Since we already know the value of Fib(1) and Fib(0), we can stop our recursion from running infinitely (whew), and start actually solving this math problem from the bottom up.

Fib(0) = 0
Fib(1) = 1

Fib(2) = Fib(1) + Fib(0)
= 0 + 1
= 1

Since we finally know Fib(2), we can solve Fib(3), and continue solving until we reach Fib(5).

Fib(3) = Fib(2) + Fib(1)
= 1 + 1
= 2

Fib(4) = Fib(3) + Fib(2)
= 2 + 1
= 3

Fib(5) = Fib(4) + Fib(3)
= 3 + 2
= 5

So Fib(5) = 5.

Please, hold your applause for the end of the guide.

The pseudocode looks something like this:

Fib(n):
	IF n == 0:
		RETURN n = 0
	ELIF n==1:
		RETURN n = 1
	ELSE:
		RETURN Fib(n – 1) + Fib(n – 2)

Example Two

Say you order pizza with friends every Monday night to keep those beginning of the week blues at bay. There's just one problem: people keep finding out about your weekly pizza group meaning you have to order more pizzas each Monday.

Putting your super sleuth skills to good use, you notice that for every four people who join the group, you need another pizza. We'll assume that everyone loves pineapple and black olive pizza. That's a pretty safe bet, so you can ignore ordering four different toppings.

If your algebra teacher has taught you anything, it's that

1. people can have some pretty ridiculous—and delicious—problems. (Mmm, pineapple.)
2. this is a linear equation.

We hear you on that second point but, for the purpose of this topic, let's think of the problem recursively.

We're going to need a base case. After all, if it's only you, you can't just order a quarter of a pizza (unless you want to get laughed off the phone by the delivery guy). Let's say the base case is:

PizzaNumber(n) = 1, n ≤ 4

If you invite three friends or fewer, order one pizza. Unless you're inviting Shmoop; then we'll need three more.

Ignoring the Shmoop outlier (Shmoutlier?), you still need to subtract towards the base case.

PizzaNumber(n) = PizzaNumber(n – 4) + 1, n > 4

Let's try this on a group of 15 pizza lovers.

PizzaNumber(15) = PizzaNumber(15 – 4) + 1

PizzaNumber(11) = PizzaNumber(11 – 4) + 1

PizzaNumber(7) = PizzaNumber(7 – 4) + 1

PizzaNumber(3) = 1

Anything less than 4 is our base case, so we can start figuring out the answer. Now let's filter back up.

PizzaNumber(7) = PizzaNumber(7 – 4) + 1
= 1 + 1
= 2

PizzaNumber(11) = PizzaNumber(11 – 4) + 1
= 2 + 1
= 3

PizzaNumber(15) = PizzaNumber(15 – 4) + 1
= 3 + 1
= 4

That's 4 pizzas for the 15 of us.

This was a linear equation

f(x) = 4x + 1

that we modeled recursively. But! What if we told you we could do the same thing with any function?

Since any function relies on the last value to find the current value, they can all work recursively.

f(x) = 4x + 1
= f(x – 1) + 4, x > 4

f(x) = 1, x ≤ 4

Pretty neat, right?