Before delving into more efficient sorting algorithms, you need to understand a critical technique used in many applications.
Recursion Defined
Recursion refers to the process of a function or method calling itself as a valid processing step. Any function or method that does this is said to be recursive. When the function or method calls itself, it is said to recur (not "recurse").
Recursion Examples
As always, a code example may help to clarify this definition. It's time to take a look at a classic example of computing the factorial of a number. From mathematics, the factorial of a number $`x`$, written as $`x!`$, is calculated by multiplying $`x`$ by every number less than or equal to $`x`$. You could write this as using a while loop:
Non-Recursive Java Method
// java
public int factorial(int x) {
int result = 1;
while (x > 1){
result *= x;
x -= 1;
}
return result;
}
Non-Recursive Python Function
# python
def factorial(x):
result = 1
for i in range(1, x + 1):
result *= i
return result
This code, which uses loops and other non-recursive control structures, is said to be imperative. Note the use of the result variable -- this is necessary to hold intermediate values as the loop iterates.
Recursive Java Method
You can also write a recursive version to solve the same problem:
// java
public int factorial(int x) {
if (x == 0 || x == 1) {
return 1;
else
return x * factorial(x-1);
}
Recursive Python Function
# python
def factorial(x):
if x == 0 or x == 1:
return 1
else:
return x * factorial(x - 1)
This version works because the value of $`x!`$ is the same as $`x * (x-1)!`$. You use the factorial() function to calculate the value of factorial(x - 1), then multiply that by x to get the final result. Since the factorial function is only defined for positive integers, you return 1 if x < 0.
Recursion Concepts
Every successful recursive algorithm has two key features:
- A terminating condition (also called the base case), which ends the recursion when the condition is satisfied.
- A recursive step, which makes the recursive call on a subset of the input field.
Colloquially, these can be stated as rules of recursion:
- You gotta stop somewhere.
- You gotta make progress towards that stopping point.
To illustrate these rules, examine the recursive factorial code again, this time with some explanatory comments added:
// java
/**
Recursive function to calculate the factorial of a non-negative integer.
@param x: Non-negative integer
@return: Factorial of x
**/
public int factorial(int x) {
// Terminating condition aka base case or escape clause
if (x == 0 || x == 1) {
return 1;
// Recursive step
else
return x * factorial(x-1);
}
# python
def factorial(x):
"""
Recursive function to calculate the factorial of a non-negative integer.
:param x: Non-negative integer
:return: Factorial of x
"""
# Terminating condition aka base case or escape clause
if x == 0 or x == 1:
return 1
else:
# Recursive step
return x * factorial(x - 1)
The terminating condition or "base case" occurs when x <= 1. It is only here that the method returns a constant result and does not make a recursive call, and the recursion stops.
The recursive step occurs when factorial(x-1) is called. It makes progress towards the terminating condition of x < 0 by subtracting 1 from x on every recursive call.
So what happens if you break one of these rules? Take a look at the following buggy code, which breaks the terminating condition rule:
// java
public int factorial(int x) {
// BUGBUG: Terminating condition will never be satisfied
if (x < x)
return 1;
else
return x * factorial(x-1);
}
# python
def factorial(x):
# BUGBUG: Terminating condition will never be satisfied
if x < x:
return 1
else:
return x * factorial(x - 1)
Since the terminating condition can never be satisfied, every time the code is called, it calls itself again with a smaller number. Since there is no stopping point, the calls continue indefinitely -- at some point, memory will be exhausted from tracking all the calls, and your program will crash.
Now take a look at code which fails to make progress:
// java
public int factorial(int x) {
if (x < 0)
return 1;
// BUGBUG: Never reduces x
else
return x * factorial(x);
}
#python
def factorial(x):
if x == 0 or x == 1:
return 1
else:
return x * factorial(x)
Here, the recursive call doesn't change x at all. This means the terminating condition never has the chance to be satisfied since x will never get closer to zero. Again, memory fills trying to keep track of all the recursive calls, and your program crashes.
Advantages and Disadvantages
One of the main advantages of recursion is the elegance of many recursive solutions. From the viewpoint of code simplicity, recursive solutions often have elegance and charm, which imperative code can lack.
Recursion is also a key technique for solving problems, which can be split into smaller problems of the same kind. Solving the smaller sub-problems and then combining the results is often called divide and conquer. As you will see, it is a key technique for sorting large datasets.
However, recursion comes with a large caveat due to the way method and function calls are implemented in most programming languages.
When a method or function is called, the program needs to remember where it was called from so it knows where to return to. This is normally accomplished by pushing the address to return to an internally managed stack called the call stack. The size of the call stack is large but limited by a combination of the runtime environment and operating system in both Java and Python. It is normally large enough for most programs. However, recursive methods and functions can quickly fill the call stack with data, even if the recursive function is properly written. When the call stack is full, no more function or method calls can be made, and your program crashes with a cryptic stack overflow error.
Tail-end Recursion
Recursive calls can appear anywhere in your methods and functions, but there is a special case that occurs when the recursive step is the final operation of the method. This is called tail-end recursion or tail recursion, and it enables an interesting optimization. Since the function returns immediately after the recursive call, compilers often treat tail-end recursive calls as simpler jumps, avoiding the normal overhead of a recursive call.
To show this, here is code which calculates the Greatest Common Divisor (GCD) between two integers using the Euclidean algorithm:
// java
public int gcd(int x, int y) {
if (y == 0)
return x;
else
return gcd(y, x % y);
}
# python
def gcd(x, y):
if y == 0:
return x
else:
return gcd(y, x % y)
The terminating condition occurs when y == 0, and the recursive step calls gcd(y, x % y). Since this recursive call is the final thing that occurs in the else branch, instead of calling gcd() as normal, the compiler can just jump back to the first line after assigning the proper parameter values, bypassing the overhead of a function call and avoiding the problem of overflowing the call stack.
To compare, here is the equivalent solution, written in imperative code:
// java
public int gcd(int x, int y) {
while (y != 0){
int temp = x % y;
x = y;
y = temp;
}
return x;
}
# python
def gcd(x, y):
while y != 0:
x, y = y, x % y
return a
Both give the same answer, but the recursive version is arguably more elegant and easily understood than the imperative version. Thanks to tail-end recursion, the first one may be optimized to the same code as the second as well.
Note that the recursive factorial() method is not tail-end recursive. Even though the recursive step is the final call, the calling function still has to multiply that result by the current value of x before it can finally return. This cannot be optimized away.
Summary: Recursion
Functions and methods which call themselves do so are called recursive. Recursive algorithms all need to stop somewhere (the terminating condition) and keep moving toward that stopping point (the recursive step). It's a great technique for implementing a divide-and-conquer approach to solving certain problems.
Now, you can learn how to use recursion to sort large datasets.