Several types of loop are available for solving algorithmic problems: the “for” loop, the while loop, and the repeat until loop. Unfortunately, these constructs are not always easy to implement. A loop’s exit condition often depends on parameters that change as the program runs, and proving that it will eventually be met is no easy matter. For aficionados of functional programming, the question does not even arise: they reject loops altogether. If you do not use variables, why iterate?
Recursion is the cure for all these ills.
An algorithm is recursive if it calls itself. Be warned: not all programming languages allow this. The classic, even clichéd, example of recursion is the factorial: the factorial of an integer n (written n!) equals n multiplied by the factorial of n – 1. Since the process has to stop somewhere, the factorial of 1 is defined as 1. This example reveals two rules that must be followed when writing a recursive procedure: there must be a termination condition (here, n = 1), and the procedure must be applied again to a "strictly smaller argument" (here, n – 1 is indeed strictly less than n). To make this completely concrete, here is the pseudocode for our procedure.
Let's step through the algorithm for n = 3.
