Recursion

In C/C++, functions can call themselves. This is called recursion, and a function that calls itself is said to be recursive. A simple example is the function factr( ) shown here, which computes the factorial of an integer. The factorial of a number N is the product of all the whole numbers from 1 to N. For example, 3 factorial is 1 × 2 × 3, or 6.

// Compute the factorial of a number using recursion.
int factr(int n) 
{
  int answer;

  if(n==1) return 1;
  answer = factr(n-1)*n;
  return answer;
}

When factr( ) is called with an argument of 1, the function returns 1; otherwise, it returns the product of factr(n–1) * n. To evaluate this expression, factr( ) is called with n–1. This process continues until n equals 1 and the calls to the function begin returning. When factr( ) finally returns to the original caller, the final return value will be the factorial of the original argument.

Programming Tip

Although powerful, recursive functions should be used with care. The recursive versions of many routines execute a bit more slowly than the iterative equivalent because of the added overhead of the repeated function calls. Many recursive calls to a function could cause a stack overrun. Because storage for function parameters and local variables is on the stack and each new call creates a new copy of these variables, the stack space could become exhausted. If this happens, a stack overflow occurs. If this happens in the normal use of a debugged recursive function, try increasing the stack space allocated to your program. When writing recursive functions, you must include a conditional statement somewhere that causes the function to return without the recursive call being executed. If you don't, once you call the function, it will call itself until the stack is exhausted. This is a very common error when developing recursive functions. Use output statements liberally during development so that you can watch what is going on and abort execution if you see that you have made a mistake.

When a function calls itself, new local variables and parameters are allocated storage on the stack, and the function code is executed with these new variables from its beginning. A recursive call does not make a new copy of the function. Only the arguments and local variables are new. As each recursive call returns, the old local variables and parameters are removed from the stack and execution resumes at the point of the recursive call inside the function. Recursive functions could be said to “telescope” out and back.