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