The core idea behind recursion is that to arrive at the final solution, a method calls itself. This might be confusing at first, so lets first give a simple example and work our way up to more complicated problems.

Before we get started, lets first talk about the basic rules for normal recursion:

  1. There must be a base case. A base case is the case where the function stops calling itself. If there is no base case (or the base case is never met), the function will continue to call itself until it will eventually throw a StackOverFlow error (which is what the famous website is named after).

  2. There must be a base case. A base case is the case where the function stops calling itself. If there is no base case (or the base case is never met), the function will continue to call itself until it will eventually throw a StackOverFlowError (which is what the famous website is named after).

  3. The function must work toward the base case. If this rule is not followed, the recursive method would never exit and throw a StackOverFlowError.

There are some other guidelines while writing recursive functions. These are not rules per-se, but rather things you should follow:

  1. The answer should be built up from all the recursive calls.

  2. Never do the same thing multiple times. (Advanced)

The Fibonacci Sequence

The first recursive function we will be studying is the Fibonacci Sequence. The Fibonacci Sequence is a sequence that starts with 1, 1 with each next element being the sum of the previous two elements.

Thus, the first 10 elements are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

To find the nth fibonacci number, you can use this function:

public int fibonacci(int n) {
	// base case
	if (n <= 2) return 1;
	// recursion
	return fibonacci(n - 1) + fibonacci(n - 2);	
}

It is relatively easy to see how this program works. If the nth Fibonacci number is simply the sum of the two previous, then why not just return the sum of the n-1th and n-2th Fibonacci numbers? This keeps going until we compute the 1st or 2nd Fibonacci number, which we already know the value of (both are 1).

This follows the first three rules:

  1. The base case is when n is 2 or less, which would answer zero.
  2. The function works towards the base case (the function calls itself with a progressively smaller n value).
  3. The function builds up the answer, since it adds up previous Fibonacci numbers to achieve a final answer.

However, this function is also very inefficient. For a better illustration of how inefficient it is, you can look at this animation of each recursive call in tree form for finding the 6th Fibonacci number:

Notice how many calls there are to the function with the same parameter (i.e. the number of calls to 3 or 4).

This is doing significantly more work then needs to be done. Why recompute the 3rd Fibonacci number so many times when you’ve already done it once?

Memoization (for advanced readers)

Memoization (not memorization) is the practice of storing previously computed answers to speed up programs.

One way of memoizing the Fibonacci function is to store the previously computed answers in an array. Every time we compute an answer, we put it in the array and every time the function is called, we check if the array has the value already computed. One implementation of this algorithm might look like

// overload this function to allow for the creation of the cache array.
public int fibonacci(int n) {
	// make the cache array have a length of n + 1, since there are n + 1 fibonacci numbers below and including it.
	int[] cache = new int[n + 1];
	// cache the first two values. this will act as our base case.
	cache[1] = 1;
	cache[2] = 1;
	// now, call the overloaded fibonacci function with our newly created cache array.
	return fibonacci(n, cache);
}
public int fibonacci(int n, int[] cache) {
	// check cache
	if (cache[n] != 0) return cache[n];
	// set cache & recursion
	cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
	return cache[n];
}

This new function is much more efficient, having a runtime of approximately O(n).

The recursion tree for this function looks like:

Memoized Fibonacci

This functions’s time complexity is O(n), because even though there are more than n calls, it scales linearly with the data. You can graph this relation with the linear equation y = 2x - 3.

Fun fact: the time complexity of the normal (non memoized Fibonacci) function is approximately O(φ^n)1, or O(e^n). φ is the golden ratio (approximately 1.6180).

Tail Recursion

Tail recursion is a recursion optimization where the last piece of code executed by the function is the recursive call. This also means no operations can be performed on the recursive call.

Generally, tail recursion involves passing an additional parameter (aka a state) into the call. This represents the current execution condition of the function. For example, if we were to write a tail recursion implementation of the Fibonacci function, we would pass in the past two Fibonacci numbers in.

When writing a tail recursion function, we must first think about what the recursive function needs to know about its current condition. For our case, the function needs to know the previous two Fibonacci numbers. Thus, our method header would look something like this:

// a is the previous number, b is the number before a.
public int fibonacci(int n, int a, int b) {
	// implement!
}

Next, we need to think about what the recursive function must do and how it might manipulate its state to get to the next state.

For our Fibonacci function, we just need to calculate the next Fibonacci number by adding the previous two states. For our next recursive call, this will be the previous number. The previous Fibonacci number (a in our method header) becomes b (2 Fibonacci numbers before this call).

As an example, if the previous two fibonacci numbers were 2 and 3, we would call our fibonacci function with the state 5, 2 (5 = 2 + 3, 2 is the previous fibonacci number).

We can then implement this function like:

// overloaded method used to start at a specific state
public int fibonacci(int n) {
	// start with the previous two numbers being the first two fibonacci numbers
	return fibonacci(n, 1, 1);
}

public int fibonacci(int n, int a, int b) {
	// base case is 3 because our starting case was after the first two fibonacci numbers
	if (n <= 3) return a + b;
	// tail recursive function
	return fibonacci(n - 1, a + b, a);
}

Our recursive tree now looks a bit weird:

Tail Recursion Tree

This is because there no longer is any actual tree since we’re calculating everything based on state. All of the information needed for the function to work is passed into it so the function doesn’t need to run more recursive calls to get that information.

Next Steps

After learning about recursion, you should try solving some of the following problems on the DMOJ Modern Online Judge:

Rounding to Fibonacci

(Challenge): Word Scrambler

Please note that these problems require basic knowledge of reading input, which you can find a brief introduction of [here].(https://www.w3schools.com/java/java_user_input.asp)

Please note that you should never prompt (i.e. ask the user to “enter x”) for input on the DMOJ Modern Online Judge.

After you’re done those problems, there are many others on Coding Bat.

Works Cited

  1. Dasdan, A. (2018). Twelve Simple Algorithms to Compute Fibonacci Numbers. arXiv preprint arXiv:1803.07199.