Embedded Files
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
Mathematical operations like Factorial or patterns like the Fibonacci Sequence.
Pathfinding algorithms like Dijkstra’s Algorithm or the A* Search Algorithm.
Efficient sorting algorithms like Merge Sort or Quick Sort
Did You Know? MOM: Mom's Organic Market is a recursive acronym
RESOURCES
Coding With John - Recursion
Alex Lee on Recursion
Computerphile on Recursion
Page updated
Google Sites
Report abuse