Recursive Algorithms

Recursive Algorithms

Recursion is a particularly powerful technique in mathematical definitions. A few familiar examples are those of natural numbers, tree structures, and of certain functions:
1. Natural numbers:
(a) 0 is a natural number.
(b) the successor of a natural number is a natural number.
2. Tree structures
(a) O is a tree (called the empty tree).
(b) If t1 and t2 are trees, then the structures consisting of a node with two descendants t1 and t2 is
also a (binary) tree.
3. The factorial function f(n):
f(0) = 1
f(n) = n × f(n - 1) for n > 0

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions. Recursive algorithms, however, are primarily appropriate when the problem to be solved, or the function to be computed, or the data structure to be processed are already defined in recursive terms. In general, a recursive program P can be expressed as a composition P of a sequence of statements S (not containing P) and P itself.