Chapter 13 – Recursion

(Updated January 13, 2025)

Table of contents

Overview
The Basics
An Example
Different Types of Recursion
Another Example
The Cost
Memoization
Exercises

Overview

We have previously determined that we often need to work while some condition exists or until some condition is met. This has always been handled using an iterative process, which we call a loop. However, there can be some cases where a loop may not be straightforward or is otherwise complicated by the logic or the data structure in use.

Recursion is essentially iterative in its design but uses a different component for control – specifically, the runtime call stack. Recursion has its roots in Lambda calculus and is the core of functional programming – both topics are well beyond the scope of this discourse.

When we use a loop, we often refer to a loop-control variable.

int x;

for (x = 0; x < 10; x++)
    System.out.println(x);

In the code above, the loop control variable is x and will determine when the loop will stop based on the condition. The variable x is likely a local variable, meaning the scope is local to the method in which it is defined. Local variables are called automatic variables. This means they are automatically created with each method's call; hence, each method call gets its own local/automatic variables.

Automatic (local) variables are created on the runtime stack (along with the argument data passed to the method) and are thrown away when the call is complete. Each call to a method is separate, with a distinct set of arguments and local variables. Each invocation is then locked in time to allow other work (subsequent calls to the same method) to proceed. When control returns to a previous time-locked call, the results from the other calls can influence (or not) the work that remains to be completed.

The call stack becomes part of the control since each method call contains point-in-time knowledge of how the problem-solving process progresses. As this big-picture view is often necessary to solve more significant problems, there is a potential need for much more than a simple loop-control variable.

This is the key to recursion.

The Basics

With recursion, there is a predisposition that the method will invoke itself directly or indirectly. In other words, the method may explicitly call itself (direct) or another method that will then call this method again (indirect).

Since the method will be asked to invoke itself again before the current call is completed, we need a mechanism to stop this. So we need a set of cases to assist with call control:

• The base case is where all additional calls will occur.
• The stopping case is the case under which we make sure no more calls occur. This begins unraveling the call stack and allows the previous calls to be completed.

An Example

Consider the obligatory Factorial calculation such that 4! = 24 (4*3*2*1) and 0! = 1. This is the most straightforward calculation in both iterative and recursive solutions. This is due to the sheer simplicity of the algorithm and why it is so popular to illustrate recursion and is shamelessly repeated here. The code in Example 1 illustrates the iterative approach.

public class FactorialIter {

    /**
     * Calculates factorial
     *
     * @param n represents n!
     * @return int result
     */
    public static int fact(int n) {

        int prod = 1;

        if (n < 0)
            throw new IllegalArgumentException("Value cannot be negative.");

        for (int i = n; i > 1; i--)
            prod = prod * i;

        return prod;
    }

    public static void main(String[] args) {
        System.out.println(fact(0));
        System.out.println(fact(4));
        System.out.println(fact(15));
    }
}

Example 1: Factorial through iteration.

The product of the reducing values of n is set to 1 to cover the 0! possibility. Otherwise, we count down from the start until we reach 1 and return the result. Simple. Now consider the version in Example 2 as an alternative solution using recursion.

public class FactorialRecurse {

    /**
     * Calculates factorial
     *
     * @param n represents n!
     * @return int result
     */
    public static int fact(int n) {

        if (n < 0)
            throw new IllegalArgumentException("Value cannot be negative.");

        if (n == 0 || n == 1)
            return 1;
        else
            return n * fact(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(fact(0));
        System.out.println(fact(4));
        System.out.println(fact(15));
    }
}

Example 2: Factorial using recursion

We are still reducing the value of n, but in this case, it is done with each subsequent call to fact(). So, each call will end up calling itself with a smaller value of n. That is until n reaches one of the stopping cases of being 0 or 1.

Now is a good time to reiterate that a recursive method comprises both a base and a stopping case. The base case is used when we know another call must be made, and the stopping case causes the calls to stop. Further, it causes all previous calls to complete in the reverse order in which they were invoked. This is because the call stack has return addresses of who did the calling placed on the top each time. All we do now is allow the calls to return, and the values get sent back to the original callers as the stack is unwound.

Figure 1: Values calculated with each call to fact().

Figure 1 shows the calls occurring as a tree. This was done to demonstrate that for each call that is made to fact(), there are two parts:

• The current value of n.
• The next call.

With multiplication implied on each row of the tree, it should be easy to see how, in the final row, the value 1 (stopping case applied) is returned up the call tree so that we end up with 2*1 returned, which results in 3*2 returned which results in 4*6 as the final value returned to fact(4).

Different Types of Recursion

There are fundamentally two major forms of recursion:

• Direct - Method/Function always calls itself. (MethodA -> MethodA -> MethodA ...)
• Indirect - Method/Function calls one or more partner Methods/Functions, which eventually end up circling back to calling the original. (MethodA -> MethodB -> MethodC -> MethodA ...)

There are four different types of direct recursion:

• Tail - performs other work before calling itself (at the tail end of the work).
• Head - calls itself (at the head end of the work) before doing anything else.
• Linear - this refers to code that only calls itself once in the body of the recursion.
• Tree - calls itself at least twice within the body of the recursion.

Now, let us discuss the differences here. The code in Example 2 is direct, linear tail recursion. Of course, we could move a few things around and make it head recursion:

  public static int fact(int n) {
    
      if ( n > 1 )
          return fact(n-1) * n;
      else if (n == 0 || n == 1)
          return 1;
      else
          throw new IllegalArgumentException("Value cannot be negative.");
    }

All we did was move where the recursive portion happens. Subsequently, we flipped the tree such that the calls now run down the left-hand side.

In the next section, we will look at tree recursion in detail.

Another Example

Consider both the iterative and recursive options of any given solution. If something is difficult to write for one or the other, then the path is likely undeniable as to what you should choose.

If something can be written relatively simply, both iteratively and recursively, begin by evaluating the number of resources each model requires to complete the task.

Consider the fundamental Fibonacci (golden ratio) sequence:

• Start with 0 and 1 as the first two numbers.
• To compute the third, you sum the first and second.
• To compute the fourth, you sum the second and third. And so on.

The first 47 Fibonacci numbers are:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711
28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578
5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141
267914296 433494437 701408733 1134903170 1836311903

The computing of the following value would overflow a 32-bit integer, so a long would need to be considered for higher Fibonacci sequences.

The Fibonacci function is written such that F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, ..., F(46) = 1836311903.

Now, an iterative program looks like this:

public class FibIter {

    /**
     * Iterative Fibonacci
     *
     * @param n the nth number
     * @return int result
     */
    public static int fib(int n) {

        if (n < 0)
            throw new IllegalArgumentException("Value cannot be negative.");

        int previous = -1;
        int current = 1;

        for (int i = 0; i <= n; i++) {
            int sum = current + previous;
            previous = current;
            current = sum;
        }
        return current;
    }

    public static void main(String[] args) {
        System.out.println(fib(46));
    }
}

Example 3: Fibonacci as an iterative solution.

A recursive one looks like this:

public class FibRecurse1 {

    /**
     * Tail tree recursive Fibonacci
     *
     * @param n the nth number
     * @return int result
     */
    public static int fib(int n) {

        if (n < 0)
            throw new IllegalArgumentException("Value cannot be negative.");

        if (n == 0 || n == 1)
            return n;
        else
            return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fib(46));
    }
}

Example 4: Fibonacci as a recursive solution.

The iterative approach is relatively straightforward and follows the rules we established earlier. The previous and current numbers are used with each iteration to compute a third. The numbers are then arranged such that the current becomes the previous, and the newly calculated one becomes the current. We do this until the correct number of iterations has occurred and then return the value.

The recursive version uses the ability of a method to call itself and uses the founded premise that we are summing the previous two Fibonacci numbers to calculate our own; therefore, it seems logical that we would add the invocations of the two values before our own, namely n-1 and n-2.

The problem is that although this seems rather logical, we have introduced one of the most poorly crafted recursive methods! For any call to be complete, it must successfully make two additional calls. Going further, the calls must eventually end where n==0 or n==1.

So, if we were to picture what a call to fib(4) might look like with all the additional calls being made, you might see it pictured as something like Figure 2.

Figure 2: Hierarchy of calls made for fib(4).

This means that 5 values will be summed, and 9 calls will be made. To calculate this, we needed to make 9 calls, compared to 5 iterations for the iterative equivalent. This means we should investigate further the work required to complete the job.

Now, here is the FibRecurse class with the additional recording of the number of calls made to fib().

public class FibRecurse2 {

    static long fibcalls;

    /**
     * Tail tree recursive Fibonacci with call tracing
     *
     * @param n the nth number
     * @return int result
     */
    public static int fib(int n) {

        fibcalls++;

        if (n < 0)
            throw new IllegalArgumentException("Value cannot be negative.");

        if (n == 0 || n == 1)
            return n;
        else
            return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        fibcalls = 0;
        System.out.println(fib(1));
        System.out.println("fibcalls = " + fibcalls);

        fibcalls = 0;
        System.out.println(fib(4));
        System.out.println("fibcalls = " + fibcalls);

        fibcalls = 0;
        System.out.println(fib(46));
        System.out.println("fibcalls = " + fibcalls);
    }
}

Example 5: Fibonacci as an iterative solution with additional code to count the number of calls.

Additionally, we are testing fib(1), fib(4) and fib(46). The output of the above is as follows:

1
fibcalls = 1
3
fibcalls = 9
1836311903
fibcalls = 5942430145

The amount of work necessary to calculate Fibonacci numbers recursively is not paying off. Of course, this is because each call made will likely result in two more.

From a Big-O perspective, this could be perceived as linear, meaning that we know that there will be about three times as many calls as the value we are searching for in a given Fibonacci slot. The reality is that it is much, much worse. To find the 47th number, we need to make nearly 6 billion method calls. That isn't very good.

So, let's try one more time. We've introduced a second method that is private and can only be invoked by fib().

There are two variables p (previous) and c (current). The fib() method calls fib2() with values of n, -1 and 1. The value of n still represents the Fibonacci number we seek. The -1 is the previous value (we have not seen any yet), and 1 is the current. One only needs to review the iterative version above to understand what has been done. We have used recursion to implement the iterative properties of the first example.

public class FibRecurse3 {

    static int fibcalls;

    /**
     * Calculate Fibonacci
     *
     * @param n the nth number
     * @return int result
     */
    public static int fib (int n) {
        return fib2(n, -1, 1);
    }

    /**
     * Tail linear recursive Fibonacci with call tracing
     *
     * @param n number to be found (reducing)
     * @param p previous number
     * @param c current number
     * @return int result
     */
    private static int fib2(int n, int p, int c) {
        fibcalls++;
        if ( n == 0 )
            return p + c;
        else
            return fib2(n-1, c, p+c);
    }

    public static void main(String [] args) {
        fibcalls = 0;
        System.out.println(fib(46));
        System.out.println("fibcalls = " + fibcalls);
    }
}

Example 6: Refactored Fibonacci recursive solution.

Although this code addresses the performance issue, it reveals that sometimes the iterative approach is possibly the better one due to its simplicity. The number of calls has been dramatically reduced.

1836311903
fibcalls = 47

The Cost

If you have not already done so, review the Big-O Notation write-up.

We mentioned Big-O earlier to put some code into perspective. We will delve into time and space complexity in iterative and recursive solutions.

Table 2: Example work with the time and space complexity.

There is a stark difference between the implementations of Factorial and Fibonacci. The Factorial solution is linear regardless of whether we choose iterative or recursive. That is to say that the number of calls in the recursive method equals the number of times through the loop in the iterative solution. At that point, it would be a question of which solution is faster and easier to maintain.

The takeaway is that, if nothing else, we must be mindful that we can approach a problem from both the iterative and recursive perspectives. Just make sure that the cost of your choice is worth the investment.

If the recursive solution is elusive, it likely is that one does not exist directly or may be very complicated to implement. This means you may have to refactor how you are approaching the solution. See the Tree code for examples of how things need refactoring.

As a final note, consider this: become acquainted with binary trees, particularly the recursive pre-, in-, and post-order processing. Now, try to find an iterative solution to that problem.

Need a hint? A stack will allow you to keep track of items visited but not ready to be printed due to your location in the tree. You store values on the stack as you loop through the left and right sub-trees.

Memoization

In trying to improve algorithms where iteration cannot be applied, there are other ways to enhance recursive situations with no solution other than tree recursion. In these situations, we can rely on knowledge we have already obtained.

Memoization is not new and was first coined in the late 1960s by Donald Michie. It is from the Latin memorandum. A memorandum was also an instrument in early office culture, where letters were sent to people highlighting important details that were not to be forgotten. This was also often expressed as a memo.

So, memoization is a collection of things we should not forget since we have already spent the capital on obtaining the knowledge.

import java.util.HashMap;

public class FibMemo {

    static long fibcalls;
    static HashMap<Integer, Integer> memo = new HashMap<>();

    /**
     * Tail tree memoized Fibonacci with call tracing
     *
     * @param n the nth number
     * @return int result
     */
    public static int fib(int n) {

        fibcalls++;

        if (memo.containsKey(n))
            return memo.get(n);

        if (n == 0 || n == 1)
            return n;

        int sum = fib(n - 1) + fib(n - 2);
        memo.put(n, sum);
        return sum;
    }

    public static void main(String[] args) {
        fibcalls = 0;
        System.out.println(fib(46));
        System.out.println("fibcalls = " + fibcalls);
    }
}

Example 7: Fibonacci recursive memoization solution.

The code in Example 7 uses a HashMap solution. Using a Map type data structure, we can store (key,value) pairs. In this case, the key is n, and value is the Fibonacci number for n.

We create a new empty Map and then calculate Fibonacci numbers. Along the way, we ask the HashMap if it has seen a key of n using containsKey(). If it has, then using the get() method of HashMap, we pass the key, and it returns the Fibonacci number for that value of n. Otherwise, when we have realized a new number has been found, we can use the put() method to add it to the HashMap for future use!

The program proceeds along these lines so that we do not waste time computing numbers we already know—we look them up.

Remember that this is only a demonstration of how we can use another tool to solve the problem of helping highly compute-intensive algorithms be more efficient. In practical design, we would not use a complex data structure like HashMap to keep track of a few Fibonacci numbers. However, you can see the power of such an approach and the freedom it offers the programming to keep moving forward.

This still significantly reduces the number of calls and is perfect for when the code is too complicated to consider refactoring.

1836311903
fibcalls = 85

Take a moment to review the time and space complexity for this solution noted in Table 2.

Exercises

(Beginner) Create a recursive method to print a String one character at a time.
(Beginner) Create a recursive method similar to Integer.ParseInt().
(Beginner) Create a recursive method to return a reversed String.
(Intermediate) Create an overloaded recursive method similar to indexOf() for a char or String.
(Intermediate) Create a recursive method to see if a string is a palindrome.
(Advanced) Create a recursive version of Bubble, Selection, or Insertion sort from Chapter 9S.