This is the second post of the series “Algorithms Demystified” (the first post “Big O Notation Demystified” can be found here).

Before we start discussing recursion it is useful to have a basic understanding of how computer memory is used by a runtime system; as an illustration we will consider the behaviour of the Java Virtual Machine (JVM) but other modern runtime systems behave similarly.

Stacks and Heaps

To optimize memory usage the JVM divides it between Heap and Stack. The Heap space is used to allocate memory dynamically to objects when they are created.

The Stack is a temporary memory block used to store local variables when a method is called. Once the method completes execution this memory is cleared, and the block is reused in a last-in, first-out (LIFO) fashion.

Recursion

It is the Stack that is of interest to us in this discussion of recursion. Recursion happens when a method makes one or more calls to itself. Programming languages that support recursion make it possible by using the LIFO Stack mechanism described above to support ordinary method calls. When a method makes a recursive call to itself its execution is suspended until the recursive call completes. Each recursive call will preserve its own copy of the method local variables.

Base Case

A recursive call must have an exit condition; this condition is called “base case”. If a base case is not defined or not reached the recursive call will propagate indefinitely eventually filling up all the memory space allocated to the Stack resulting in what is called a Stack Overflow which typically causes a program to crash.

An Example

There are several computing problems that can be solved by using recursion, one of which is the mathematical factorial function denoted as n!. The factorial function is defined as the product of positive integers from 1 to n (by convention the factorial of zero is one).
Let’s take as an example the factorial of 4:

4! = 4 * 3 * 2 * 1 = 24

We can implement the factorial function as a Java method as follows:

public static int factorial(int x) {
   // input validation
   if (x < 0) throw new IllegalArgumentException("Argument must be positive integer");
   // base case
   else if (x == 0) { return 1; }
   // recursive call
   else return x * factorial(x - 1);
}

To understand how recursion works suppose we call the factorial method above passing as argument the integer number 4. When execution reaches the recursive call the method suspends and calls itself with the argument subtracted by 1:

Call factorial(4) suspended (4 – 1 = 3)
Call factorial(3) suspended (3 – 1 = 2)
Call factorial(2) suspended (2 -1 = 1)
Call factorial(1) suspended (1 – 1 = 0)
Call factorial(0) base case: return 1

In the last call factorial(0) we reach the base case and all suspended recursive calls return:

factorial(0) returns 1
factorial(1) returns 1 * 1 = 1
factorial(2) returns 2 * 1 = 2
factorial(3) Return 3 * 2 = 6
Factorial(4) returns 4 * 6 = 24

The last return value 24 is the value of 4! as expected.

Conclusion

Computing problems that can be solved using recursion can also be solved iteratively. The advantage of using iteration over recursion is that the latter has higher space and time complexity. On the other hand recursion provides a more intuitive and cleaner solution to certain class of problems such as exploring tree structures.

Icons made by Smashicons from www.flaticon.com