Lecture 16: Recursive programming

Recursive

A function is recursive if it is defined in terms of itself (i.e., it calls itself)

Example 1: Factorial

The classic example is the calculation of the factorial function n! We might do this with a loop, as described in lectures 11 and 12:
int factorial(int n)
 /* returns n! */
{
  int i, result;

  result = 1;        /* initialize the variable */
  for (i=1; i<=n; i++)
    result = i*result;
  return(result);
}
This function, indeed, will return the factorial of the argument, for instance factorial(5) = 120. Check this.

A much more interesting solution is via defining the function factorial in terms of itself, just as we have learned in school,

  n! = n*(n-1)!

Let's do exactly that:
int factorial(int n)
 /* should return n! */
{
    /* the value to be returned is expressed in terms of itself: */
  factorial = n*factorial(n-1);
}
 
This function is already nearly correct. The only problem is that it will never stop calling itself. For instance, we can call it with factorial(4), which will then try to calculate 4*factorial(3) and hence call factorial(3). factorial(3) will try to calculate 3*factorial(2), which will call factorial(2), ... which will call factorial(1) ... which will call factorial(0) ... which will call factorial(-1) ... which will call factorial(-2) ... and this will never end. The program will never return anything and the computer will crash, probably generating a so-called "stack overflow" error. Clearly we have to build in a way to stop calling itself. Now remember that in the mathematical way of defining a function in terms of itself we also always had to build in a stop, for the factorial function, this was

 1! = 1

Let's also built this into our function:
int factorial(int n)
 /* returns n! */
{
  if (n==1)
    return(1);
  else
    return(n*Factorial(n-1));
}

The idea we should learn from this is that we should give it a possibility to come up with an answer and exit the recursive calculation. Just like the way we had to give a loop the possibility to end we should also give this possibilty to recursive functions. If not, the program will continue forever (or crash).

Example 2: Fibonacci

Remember from the practical lessons, the definition of a Fibonacci number is in terms of itsef:
  fn = fn-2 + fn-1
with the stopping conditions
  f1 = 1
  f2 = 1
For instance,
  f3 = 1 + 1 = 2
  f4 = 1 + 2 = 3
  f5 = 2 + 3 = 5
  f6 = 3 + 5 = 8
  f7 = 5 + 8 = 13

We can implement this in a function, note the stopping condition:
int fibonacci(int n)
{
  if ((n==1) || (n==2))
    return(1);
  else
    return(fibonacci(n-2) + fibonacci(n-1));
}

Variables

Variables that are declared inside recursive functions are all local. Moreover, everytime the function is called, a new instance of the variable is created that exists until the function finishes. (in C we can prevent this with the word "static" in front of the variable declaration). Each of these variables, although they have the same name, will point to a different space in memory. As an example, let's create a local variable in our factorial function:
int factorial(int n)
{
  int m, result;

  m = 2*n;
  printf("%d ", m);
  if (n==1) then
    result = 1;
  else
    result = n*factorial(n-1);
  printf("%d ", m);
  return(result);
}
When we call this function with argument 3 the following will happen:
 
instruction
variables
factorial(3) is called  
  variables n, m and result are created m=* r=* n=*
  3 is assigned to n (from the function call)
  2*3 is assigned to m		 m=6 r=* n=3
  factorial(2) is called m=6 r=* n=3
    variables n, m and result are created
          (new ones; different from variables above!)		 m=* r=* n=* m=6 r=* n=3
    2 is assigned to n (from the function call)
    2*2 is assigned to m		 m=4 r=* n=2 m=6 r=* n=3
    factorial(1) is called m=4 r=* n=2 m=6 r=* n=3
      variables n, m and result are created
          (different than the ones above)		 m=* r=* n=* m=4 r=* n=2 m=6 r=* n=3
      1 is assigned to n (from the function call)
      2*1 is assined to m		 m=2 r=* n=1 m=4 r=* n=2 m=6 r=* n=3
      ... we reach the stop condition and result = 1; m=2 r=1 n=1 m=4 r=* n=2 m=6 r=* n=3
      The value of m is writen: 2 m=2 r=1 n=1 m=4 r=* n=2 m=6 r=* n=3
      The value of result (1) is returned to the calling instruction
      we exit factorial(1), the last n, m and result are destroyed		 m=4 r=* n=2 m=6 r=* n=3
    result is calculated: n*factorial(n-1) becomes
    n*'value just returned' -> 2*1 = 2		 m=4 r=2 n=2 m=6 r=* n=3
    The value of m is written: 4 m=4 r=2 n=2 m=6 r=* n=3
    The value of result (2) is returned to the calling instruction
    we exit factorial(2), the last n, m and result are destroyed		 m=6 r=* n=3
  result is calculated: n*factorial(n-1) becomes
  n*'value just returned' -> 3*2 = 6		 m=6 r=6 n=3
  The value of m is written: 6 m=6 r=6 n=3
  The value of result (6) is returned to the calling instruction
  we exit factorial(3), the variables n, m and result are destroyed		  
the value returned from factorial(3) is 6  

r means variable 'result'
* means undetermined value
What we learn from this is that the variables are not static objects in memory, pointing to certain addresses, but instead, the variables are created at the time we run the program. Each time we enter the function, new ones are created that live until we exit the function. Moreover, as can be seen in the example above, the last variables created are the ones used locally.
(This only applies to languages that have dynamic variables, like C or PASCAL)

Quick Test

To test your knowledge of what you have learned in this lesson, click here for an on-line test.
Peter Stallinga. Universidade do Algarve, 22 November 2002