A recursive function is called a tail recursive function if all the recursive calls to itself in the function are the last operations. I say it like there are multiple calls and all of them must be the last operations. How is that possible? I mean there can be different calls from different conditional branches of the code inside the function. However, whenever the function calls itself that must be the last operation in that conditional branch of the function. For example, take our binary search algorithm again:

   private static <E extends Comparable<E>, F extends E> int binarySearch( 
        E[] sortedValues, F valueToSearch, int start, int end) { 
        if(start>=end){ 
            return -1; 
        } 
        int midIndex = (end+start)/2; 
        int comparison = sortedValues[midIndex].compareTo(valueToSearch); 
        if(comparison==0){ 
            return midIndex; 
        }else if(comparison>0){ 
            return binarySearch(sortedValues, valueToSearch, start, midIndex); 
        }else{ 
            return binarySearch(sortedValues, valueToSearch, midIndex+1, end); 
        } 
    }

Note that the function calls itself in two different conditional branches. However, in each branch, the recursive call is the last operation. There is nothing to be done after the call to itself. This is a tail recursive function.

Tail recursive functions can be turned into a loop absolutely mechanically. In fact, all functional language compilers do this automatically during compiler optimization. The Java compiler, however, does not do this because Java generally prefers loops over recursion in the code, at least until very recently. But we can do this conversion by ourselves.

The idea is that since there are no more operations after the recursive call, the program does not have to remember the values of the variables of the calling function. So, they can simply be overwritten by the values of the same variables of the called function instead, and we just have to process the code of the function again. So, the following is the mechanical procedure to achieve this:

Wrap the entire content in an infinite while loop.

Replace all recursive calls by updating the values of the parameters to the values that are passed in the recursive calls.

The following shows this update in the binary search algorithm:

    private static <E extends Comparable<E>, F extends E> int binarySearchNonRecursive( 
        E[] sortedValues, F valueToSearch, int start, int end) { 
        while(true) { 
            if (start >= end) { 
                return -1; 
            } 
            int midIndex = (end + start) / 2; 
            int comparison = sortedValues[midIndex]
                               .compareTo(valueToSearch); 
            if (comparison == 0) { 
                return midIndex; 
            } else if (comparison > 0) { 
                end = midIndex; 
            } else { 
                start = midIndex + 1; 
            } 
        } 
    }

Note that we updated only those arguments that changed, which is only one update per branch in this case. This will produce the exact same result as the earlier function, but now it would not cause a stack overflow. This conversion is not really required in case of a binary search though, because you need only lg n steps to search an array of length n. So, if your allowed depth of invocation is 1000, then you can search in an array of maximum size of 21000 elements. This number is way more than the total number of atoms in the entire universe, and hence we will never be able to store an array of that enormous size. But the example shows the principle of converting a tail recursion into a loop.

Another example is the insertElementSorted function, used in our insertion sort algorithm:

          public static <E extends Comparable<E>> void insertElementSorted( 
            E[] array, int valueIndex) { 

              if (valueIndex > 0 && array[valueIndex].compareTo(array[valueIndex - 1]) < 0) { 
                swap(array, valueIndex, valueIndex - 1); 
                insertElementSorted(array, valueIndex - 1); 
        } 

    }

Note that there is no operation pending after the recursive call to itself. But we need to be a little more careful here. Note that the invocation only happens inside a code branch. The else case is implicit here, which is else { return; }. We need to make it explicit in our code first, as shown below:

     public static <E extends Comparable<E>> void insertElementSorted( 
     E[] array, int valueIndex) { 

        if (valueIndex > 0 && array[valueIndex].compareTo(array[valueIndex - 1]) < 0) { 
            swap(array, valueIndex, valueIndex - 1); 
            insertElementSorted(array, valueIndex - 1); 
        } else{
         return;
        } 
     }

Now we can use our old technique to make it non-recursive, that is, to wrap it in an infinite loop and replace recursive calls with argument updates:

   public static <E extends Comparable<E>> void insertElementSortedNonRecursive( 
        E[] array, int valueIndex) { 
        while(true) { 
            if (valueIndex > 0 && array[valueIndex].compareTo(array[valueIndex - 1]) < 0) { 
                swap(array, valueIndex, valueIndex - 1); 
                valueIndex =  valueIndex – 1; 
            }else{ 
                return; 
            } 
        } 

    }

This gives the exact same result as the previous recursive version of the function. So, the corrected steps would be as follows:

By single recursion, I mean that the function invokes itself at most once per conditional branch of the function. They may be tail-recursive, but they are not always so. Consider the example of the recursion of our insertion sort algorithm:

   public static <E extends Comparable<E>> void insertionSort( 
        E[] array, int boundary) { 
        if(boundary==0){ 
            return; 
        } 
        insertionSort(array, boundary-1); 
        insertElementSorted(array, boundary); 
    }

Note that the function calls itself only once, so it is a single recursion. But since we have a call to insertElementSorted after the recursive call to itself, it is not a tail recursive function, which means that we cannot use the earlier method. Before doing this though, let's consider a simpler example. Take the factorial function:

    public static BigInteger factorialRecursive(int x){ 
        if(x==0){ 
            return BigInteger.ONE; 
        }else{ 
            return factorialRecursive(x-1).multiply(BigInteger.valueOf(x)); 
        } 
    }

First, note that the function is singly recursive, because there is at most one recursive call per branch of the code. Also, note that it is not tail recursive because you have to do a multiplication after the recursive call.

To convert this into a loop, we must first figure out the actual order of the numbers being multiplied. The function calls itself until it hits 0, at which point, it returns 1. So, the multiplication actually starts from 1 and then accumulates the higher values.

Since it accumulates the values on its way up, we need an accumulator (that is a variable storing one value) to collect this value in a loop version. The steps are as follows:


What is the initial value of the accumulator prod? It is the same as the value that is returned in the exit branch of the recursion, that is, 1. What is the highest value being multiplied? It is x. So we can now convert it to the following loop:

   public static BigInteger factorialRecursiveNonRecursive(int x){ 
        BigInteger prod = BigInteger.ONE; 
        for(int i=1;i<=x;i++){ 
            prod = prod.multiply(BigInteger.valueOf(x)); 
        } 
        return prod; 
    }

Now let's consider the insertionSort algorithm. What is the accumulator? It is the same thing that would be the final output, that is, an array of sorted elements. What is the starting value? It is the same that is returned in the recursive version in the exit branch. This is an array of length zero. What is the final value? The array of sorted elements of the length provided to sort. Again, just like our recursive version, we represent these partial arrays with, simply, a boundary value. So, the code is as follows:

    public static <E extends Comparable<E>> void insertionSortNonRecursive( 
        E[] array) { 
        for(int boundary = 0;boundary<array.length;boundary++) { 
            insertElementSortedNonRecursive(array, boundary); 
        } 
    } 

Note that in this case, the function return type is void. But what we are really returning is the sorted array; we just resorted to modifying the same array to avoid creating duplicate arrays.

The most general case is the multiple recursion, that is, the function calls itself multiple times in the same conditional branch of the function. This case cannot be done without a stack. In case of a recursive call, we use the method-invocation stack. Otherwise, we can even use an external stack. Since we do not have such an example in this chapter, we defer its explanation to the next chapter, where we will have an example.