## 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 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:

Examples of Recursion

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

RESOURCES

Coding With John - Recursion

Alex Lee on Recursion

Computerphile on Recursion