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