Recursion

1. Introduction

Recursion is a technique that allows us to break down a problem into one or more subproblems that are similar in form to the original problem.

2. Example: The Factorial

Recall that factorial, which is written n!, has the following definition:

   n! = 1 * 2 * 3 * .... * (n-2) * (n-1) * n

We can use this definition to write:

int fact(int n) {
   int i;
   int result;
  
   result = 1;
   for (i = 1; i <= n; i++) {
      result = result * i;
   }
   return result;
}

We can write a function that uses recursion as follows:

int fact(int n) {
    if (n == 1) return 1;
    return n * fact(n - 1);
}

Comparing the two versions:

The iterative version has two local variables; the recursive version has none.
The iterative version has three statements; the recursive version has one.
The iterative version must save the solution in an intermediate variable before it can be returned; the recursive version calculates and returns its result as a single expression.

Recursion simplifies the fact function! It does so by making the computer do more work, so that you can do less work.

3. Definitions

The recursive functions are characterized based on:

whether the function calls itself or not (direct or indirect recursion).
whether there are pending operations at each recursive call (tail-recursive or not).
the shape of the calling pattern -- whether pending operations are also recursive (linear or tree-recursive).

Direct Recursion:

A function is directly recursive if it contains an explicit call to itself. For example, the function

int foo(int x) {

   if (x <= 0) return x;

   return foo(x - 1);
}

includes a call to itself, so it's directly recursive. The recursive call will occur for positive values of x.

Indirect Recursion:

A function foo is indirectly recursive if it contains a call to another function which ultimately calls foo.

The following pair of functions is indirectly recursive. Since they call each other, they are also known as mutually recursive functions.

int foo(int x) {

   if (x <= 0) return x;

   return bar(x);
}

int bar(int y) {
   return foo(y - 1);
}

Tail Recursion:

A recursive function is said to be tail recursive if there are no pending operations to be performed on return from a recursive call.

Tail recursive functions are often said to "return the value of the last recursive call as the value of the function." Tail recursion is very desirable because the amount of information which must be stored during the computation is independent of the number of recursive calls. Some modern computing systems will actually compute tail-recursive functions using an iterative process.

The "infamous" factorial function fact is usually written in a non-tail-recursive manner:

int fact (int n) { /* n >= 0 */

   if (n == 0)  return 1;

   return n * fact(n - 1);
}

Notice that there is a "pending operation," namely multiplication, to be performed on return from each recursive call. Whenever there is a pending operation, the function is non-tail-recursive. Information about each pending operation must be stored, so the amount of information is not independent of the number of calls.

The factorial function can be written in a tail-recursive way:

int fact_aux(int n, int result) {

   if (n == 1) return result;

   return fact_aux(n - 1, n * result)
}


int fact(n) {

    return fact_aux(n, 1);
}

The "auxiliary" function fact_aux is used to keep the syntax of fact(n) the same as before. The recursive function is really fact_aux, not fact. Note that fact_aux has no pending operations on return from recursive calls. The value computed by the recursive call is simply returned with no modification. The amount of information which must be stored is constant (the value of n and the value of result), independent of the number of recursive calls.

Linear and Tree Recursion:

Another way to characterize recursive functions is by the way in which the recursion grows. The two basic ways are "linear" and "tree."

A recursive function is said to be linearly recursive when no pending operation involves another recursive call to the function.

For example, the "infamous" fact function is linearly recursive. The pending operation is simply multiplication by a scalar, it does not involve another call to fact.

A recursive function is said to be tree recursive (or non-linearly recursive) when the pending operation does involve another recursive call to the function.

The Fibonacci function fib provides a classic example of tree recursion. The Fibonacci numbers can be defined by the rule:

   fib(n) = 0  if n is 0,
          = 1  if n is 1,
          = fib(n-1) + fib(n-2) otherwise

For example, the first seven Fibonacci numbers are

   Fib(0) = 0   
   Fib(1) = 1   
   Fib(2) = Fib(1) + Fib(0) = 1
   Fib(3) = Fib(2) + Fib(1) = 2
   Fib(4) = Fib(3) + Fib(2) = 3
   Fib(5) = Fib(4) + Fib(3) = 5
   Fib(6) = Fib(5) + Fib(4) = 8

This leads to the following implementation:

int fib(int n) { /* n >= 0 */

   if (n == 0) return 0;

   if (n == 1) return 1;

   return  fib(n - 1) + fib(n - 2);
}

Notice that the pending operation for the recursive call is another call to fib. Therefore fib is tree-recursive.

4. Converting Recursive Functions to be Tail Recursive

A non-tail recursive function can often be converted to a tail-recursive function by means of an "auxiliary" parameter. This parameter is used to form the result. The idea is to attempt to incorporate the pending operation into the auxiliary parameter in such a way that the recursive call no longer has a pending operation. The technique is usually used in conjunction with an "auxiliary" function. This is simply to keep the syntax clean and to hide the fact that auxiliary parameters are needed.

For example, a tail-recursive Fibonacci function can be implemented by using two auxiliary parameters for accumulating results. It should not be surprising that the tree-recursive fib function requires two auxiliary parameters to collect results; there are two recursive calls. To compute fib(n), call fib_aux(n 1 0)

int fib_aux(int n, int next, int result) {

  if (n == 0) return result;
  return fib_aux(n - 1, next + result, next);
}

The tree recursive fib() method is "Big O 2^n" (O(2^n)) algorithm. In other words as n increases the problem size roughly doubles. On the other hand, a linearly recursive algorithm would be O(n). In other words, the amount of work required roughly increases linearly.

References: Thomas A. Anastasio, Richard Chang.