The Coder's Handbook

Recursion

WHAT IS RECURSION?

Definition


Recursion is when you write a method that calls itself. It’s a tricky concept, but can be used to solve a lot of problems.


Let’s first consider a specific example, defining the mathematical operation of factorial.

void factorial (int n)

{

if (n == 0) // Base Case

{

return 1;

}

else // Recursive Case

{

return n * factorial(n-1);

}

}

Base Case and Recursive Case

A recursive method always has two parts:


  • The base case handles what happens when you get to the “bottom” or end of the recursion. Without a base case, you’d end up with infinite recursion. Sometimes, you’ll write a method with multiple base cases.

  • The recursive case connects your current step to the next step.

The Stack


To understand how this works, you have to understand The Stack.


The stack is a structure that every method call is placed on behind the scenes, and is stored in your computer’s RAM.


It is last-in-first-out, meaning you have to resolve the most recently called method before you finish the one that called it.


Consider factorial(5):


factorial(5)

5 * factorial (4)

5 * 4 * factorial (3)

5 * 4 * 3 * factorial (2)

5 * 4 * 3 * 2 * factorial (1)

5 * 4 * 3 * 2 * 1 * factorial (0) ← this hits the base case, and it begins to “unravel”

5 * 4 * 3 * 2 * 1 * 1

5 * 4 * 3 * 2 * 1

5 * 4 * 3 * 2

5 * 4 * 6

5 * 24

120


If you write code that never reaches the base case, you have infinite recursion. This will cause your program to run out of memory, and cause a StackOverflowError.


Below: A visualization of how a stack works using cards in "Magic The Gathering."

Method calls in Java work the same way - last in, first out.

WHY NOT LOOPS?

Ways To Repeat Things


When you want to repeat something in Java, you have two choices:


  • Using iteration means using a loop. This is likely going to be the most straightforward way to solve most problems that need repetition. It’s very good for problems that are linear.


  • Using recursion is often simpler, shorter, and more elegant for specific types of problems. Usually these problems follow a repeated pattern, but aren’t linear.


Examples of Recursion




Did You Know? MOM: Mom's Organic Market is a recursive acronym

RESOURCES

Alex Lee on Recursion

Computerphile on Recursion

Martin and the Dragon: A Tale of Recursion (Read in Class)