Environments and tail recursion

Environments

As mentioned previously, when a method is called, its code is evaluated with its own set of variables, consisting of those given as the arguments to the method, and any extra ones declared as local variables to the method. This is referred to as its environment. It is important to note that a variable with a particular name in an environment is not the same variable as one of the same name in the environment of the method from which it was called.

For example, suppose we have the code: 

public static void f(int a, int b)
{
 int c,d;
 code1
 d = g(a,c,6);
 code2
}

public static int g(int a, int k, int b)
{
 int j;
 code3
 return j;
}
what happens in a call f(7,8) is that an environment is set up with a having the value 7, b having the value 8, and c and d unallocated (in Java if you try to use a variable at a point where it might not have been allocated a value, the compiler will give you an error message when you try to compile the code). The code code1 is evaluated in this environment, meaning it has full access to the variables a, b, c and d. By the time program execution gets to the statement d = g(a,c,6), c must have been given a value (otherwise the code would not have compiled), and a and b may have had their values changed. Note that some programming languages do not protect you against the use of variables that have not been allocated a value, and this is a common source of programming errors.

When the call to g(a,c,6) is evaluated, the execution of the code for the call f(7,8) is suspended, waiting for the code of the call g(a,c,6) to finish. When it does, the value which this call returns is put in variable d in the call to f(7,8)'s environment, and then code2 is executed.

The call to g(a,c,6) has its own environment with variables a, k, b and j. Note the a and b here are completely separate from the a and b in the call f(7,8), even though it happens that a in the call g(a,c,6) is matched with a from the call f(7,8) so it starts off with the same value. When code3 has finished executing in this new environment, whatever at that point is in variable j in that new environment is copied into d in the old environment of the call f(7,8) and then code2 is executed in that old environment (with the changed value of d).

This can be illustrated diagrammatically, the dotted arrow showing the idea of execution returning to the code for f and executing code2 when it has finished executing the call g(a,c,6), and the d=j on the dotted arrow showing the idea of d in the environment for the call to f being set to the value of j in the environment to the all to g by the return statement in g:

Note that in this diagram, and the others like it below, the environment at the top is the current environment, and making a method call can be considered as creating a new environment and stacking that on top of the stack of environments.

Environments with recursion

Now let us consider a simple recursive example, the one often used to introduce the idea of recursion, factorial. The factorial of a number is the number multiplied by one less than the number, multiplied by two less than the number, ..., down to one. So, for example, the factorial of 5 (often denoted by 5!) is 5×4×3×2×1. It is easy to see that in general the factorial of n is the n multiplied by the factorial of n-1, with the base case being that the factorial of 0 is 1. So this gives us the Java method: 
public static int fact(int n)
{
 if(n==0)
    return 1;
 else
    return n*fact(n-1);
}
For the purpose of illustration, we will break the single statement return n*fact(n-1) into the component steps that in fact make it up: subtract 1 from n, find the factorial of the result of doing that, multiply the result of doing that by n and return the result of doing that: 
public static int fact(int n)
{
 if(n==0)
    return 1;
 else
    {
     int n1, m, r;
     n1 = n-1;
     r = fact(n1);
     m = n*r;
     return m;
    }
}
The more concise version just does not give names to these local variables that hold intermediate results which here we call n1, m and r.

So if we are evaluating fact(5), we will have an environment in which the variable n holds 5. We set the variable n1 in this environment to 4. Then we make a recursive call to fact, suspending the code 

r = result of recursive call;
m = n*r;
return m;
until that recursive call has finished. That can be shown diagrammatically as:

But the execution of fact(4) has its own environment with its own n, n1, m and r, with its n initialised to 4. This will result in a call to fact(3) and a suspended multiplication and return waiting for that call to give its value:

So you can see a stack of suspended multiplications and returns is built up.

Tail recursion

Now let us consider an alternative piece of code for calculating the factorial of a number: 
public static int fact(int n)
{
 return fact(n,1);
}

private static int fact(int n,int acc)
{
 if(n==0)
    return acc;
 else
    return fact(n-1,n*acc);
}
The call fact(5) just returns the value of the call fact(5,1) where the two-argument method fact is the private method that does all the work in calculating the factorial If we break down the statement with the recursive call into its component parts, introducing variables to hold the intermediate values as before, we get the following for the two-argument method fact: 
private static int fact(int n,int acc)
{
 if(n==0)
    return acc;
 else
    {
     int n1, m, r;
     n1 = n-1;
     m = n*acc;
     r = fact(n1,m)
     return r;
    }
}
Now, the only code after the recursive call is the return statement. Instead of a stack of multiplications and return statements building up as recursive calls are made, just a stack of return statements is built up, with the variable r in each environment being set to the value of the variable r from the environment of its recursive call:

Now, the variables n, acc, n1 and m are not used following the recursive call. Therefore there is no need to have a separate environment to keep them, we could just re-use the old variables of the same name from the previous environment. The value of r in each environment is just set to the value of r from the recursive environment, so again we could just use one variable called r. Java doesn't allow us to have the variable in a method call mean the same piece of memory as the variable in the method it is called from (other languages do allow this, technically called call by reference, if you are familiar with Pascal, for example, it is what that language calls a var parameter). But this is not necessary, because we can have just one environment by expressing the algorithm using iteration rather than recursion. What was a recursive call becomes another execution of the loop, with the loop test being the negation of the condition that gives us the base case. Since the value returned by the base case is the value returned by the whole computation, we return that as the result when the loop has finished. So here is the method converted to iteration: 

private static int fact(int n,int acc)
{
 int n1, m, r;
 while(n!=0)
    {
     n1 = n-1;
     m = n*acc;
     n = n1;
     acc = m;
    }
 r = acc;
 return r;
}
The assignments n = n1 and acc = m represent what was the passing of parameters to the recursive call. There is no need to have the separate variables n1, m and r, so we could make this: 
private static int fact(int n,int acc)
{
 while(n!=0)
    {
     acc = n*acc;
     n = n-1;
    }
 return acc;
}
Also, there is no need to have a separate private method, since there is no recursive call to this method so its code might as well be put inside the code for the public fact method, giving: 
public static int fact(int n)
{
 int acc=1;
 while(n!=0)
    {
     acc = n*acc;
     n = n-1;
    }
 return acc;
}
This form of recursion which can be converted easily in this way to iteration is known as tail recursion. The important thing about tail recursion is that the recursive call is the last thing that is done in the method, and its result is returned as the result of the method.

The recursion in our binary search code was of this tail recursive form. So we can convert that code to code that uses iteration: 

public static boolean search(int n,int[] a)
{
 int from=0, to=a.length;
 int mid=(from+to)/2;
 while(from!=to&&a[mid]!=n)
    {
     if(a[mid]>n)
        to=mid;
     else
        from=mid+1;
     mid=(from+to)/2;
    }
 return from!=to;
}
In the recursive version, mid is calculated before the test whether a[mid]=n which determines whether we have reached one of the base cases. In order for that test to appear in the condition of the while loop, we have put it at the end of the body of the loop, so the body of the loop actually contains the first part of the recursive call. A calculation of mid is also needed before the loop to give it an initial value for use in the test. An alternative in which the loop more directly reflects the code in the recursive call would be to use return to "jump out of the middle" of the loop: 
public static boolean search(int n,int[] a)
{
 int from=0, to=a.length;
 while(from!=to)
    {
     int mid=(from+to)/2;
     if(a[mid]==n)
        return true;
     else if(a[mid]>n)
        to=mid;
     else
        from=mid+1;
    }
 return false;
}

Iteration to recursion

 It is always possible to do the transformation the other way round, and transform an iterative method to one which uses tail recursion to accomplish the same algorithm. Here, for example, is a version of selection sort which uses iteration rather than recursion: 
 public static void sort(int[] a)
 // Sort array a
 {
  sort(0,a);
 }

 private static void sort(int i,int[] a)
 // Sort the portion of array a starting from position i
 {
  if(i<a.length-1)
     {
      int pos = smallestPosFrom(i,i+1,a);
      swap(a,i,pos);
      sort(i+1,a);
     }
 }

 private static int smallestPosFrom(int pos,int j,int[] a)
 // Return the index of the smallest element in the section of
 // array a from that indexed j to the end of the array
 // or a[pos] if that is smaller
 {
  if(j==a.length)
     return pos;
  else 
     {
      if(a[j]<a[pos])
         pos=j;
      return smallestPosFrom(pos,j+1,a);
     } 
 }

 private static void swap(int[] a,int pos1, int pos2)
 // Swap the elements indexed pos1 and pos2 within array a
 {
  int temp;
  temp = a[pos1];
  a[pos1] = a[pos2];
  a[pos2] = temp;
 }
In this case, there is not even a chain of returns when the recursive call to sort hits the base case, since this algorithm works destructively by changing the contents of the array. When the base case is reached, the contents of the array are sorted. Note that although there will be a separate variable a in the environment for each recursive call, each of these will refer to the same array. This is the situation showing the environments of two recursive calls:

Converting iteration to tail recursion doesn't give us any advantage in Java. The algorithm will have the same order of efficiency, but will be a little slower due to the overhead of making the method calls. It is a technique which is used, however, when programming using declarative languages.

The implicit stack of recursion

An interesting use of recursion avoids the problem we saw previously where if you wanted to enter a sequence of numbers to be stored in an array you had to specify the size of the array first. Here is a version of the program that reads numbers into an array where you don't have to specify the number in advance. You just carry on entering numbers until you enter a blank line instead of a number, which indicates you have finished: 
import java.io.*;
class SortIntArrayIt4
{

 public static void main(String[] args)
 throws IOException
 // Illustrates use of recursion to read a number of integers into
 // an array, without specifying how many in advance
 {
  int n;
  int[] array;
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  array = readInts(0,in);
  System.out.println("The array you entered is:");
  System.out.println(arrayToString(array));
  sort(array);
  System.out.println("After sorting, the array is:");
  System.out.println(arrayToString(array));
 }

 public static int[] readInts(int count,BufferedReader in)
 throws IOException
 {
  System.out.print("Enter integer "+count+" or new line to halt: ");
  String line=in.readLine();
  if(line.equals(""))
     return new int[count];
  else
     {
      int n = Integer.parseInt(line);
      int[] a = readInts(count+1,in);
      a[count]=n;
      return a;
     }
 }

 private static String arrayToString(int[] a)
 {
  String str="[";
  if(a.length>0)
     {
      str+=a[0];
      for(int i=1; i<a.length; i++)
         str+="|"+a[i];
     }
  return str+"]";
 }

 public static void sort(int[] a)
 // Sort the contents of array a in ascending numerical order
 {
  for(int i=0; i<a.length-1; i++)
     {
      int temp,pos=i;
      for(int j=i+1; j<a.length; j++)
         if(a[j]<a[pos])
            pos=j;
      temp = a[i];
      a[i] = a[pos];
      a[pos] = temp;
     }
 }

}
It is the method readInts here which is of interest, the rest is stuff you have seen before. The method readInts takes a BufferedReader object, so it can read, and an integer count. It reads an unspecified number of integers ending when a blank line is given in response to the prompt for another integer, and returns an array of length count plus the number of integers read, with the integers stored in order from the countth cell of the array onwards.

What is actually happening here is that the number read plus its position in the array is stored in the environment of each recursive call, waiting for the recursive call it made to return an array with only the later positions filled which is then filled with one more number. So the whole array is filled backwards from numbers stacked up in the environment. Here is a diagram showing the situation after reading three numbers, assuming those numbers are in order 42, 69 and 35:

Matthew Huntbach

Last modified: 22 January 2003