This book has shown many examples of procedures and functions, as well as
programs that call them. You know that a function can call another function;
that is, a statement in the body of a function F contains a call
of another function G. What would happen if a statement in
F contained a call of F? This situation--a function
or procedure calling itself--is not only permitted but in fact is very
interesting and useful. The concept of a subprogram--a function or a
procedure--calling itself is a mathematical concept called recursion,
and a subprogram that contains a call to itself is called a recursive
subprogram.
Recursion can be an alternative to iteration (looping), although a recursive solution to a given problem uses somewhat more computer time and space than an iterative solution to the same problem; this is due to the overhead for the extra procedure calls. However, in many instances the use of recursion enables us to specify a natural, simple solution to a problem that would otherwise be difficult to solve. For this reason, recursion is an important and powerful tool in problem solving and programming.
Copyright © 1996 by Addison-Wesley Publishing Company, Inc.