|
|
 |
|
|
|
|
Infinite Recursion The situation in which a function calls itself over and over endlessly. |
|
|
|
|
|
|
|
|
In actuality, recursive calls can't go on forever. Here's the reason. When a function is called, either recursively or nonrecursively, the computer system creates temporary storage for the actual parameters and the function's (automatic) local variables. This temporary storage is a region of memory called the run-time stack. When the function returns, its parameters and local variables are released from the run-time stack. With infinite recursion, the recursive function calls never return. Each time the function calls itself, a little more of the run-time stack is used to store the new copies of the variables. Eventually, all the memory space on the stack is used. At that point, the program crashes with an error message such as RUN-TIME STACK OVERFLOW (or the computer may simply hang). |
|
|
|
|
|
|
|
|
Recursive Algorithms with Simple Variables |
|
|
|
|
|
|
|
|
Let's look at another example: calculating a factorial. The factorial of a number N (written N!) is N multiplied by N - 1, N - 2, N - 3, and so on. Another way of expressing factorial is |
|
|
|
|
|
|
|
|
This expression looks like a recursive definition. (N - 1)! is a smaller instance of N!that is, it takes one less multiplication to calculate (N - 1)! than it does to calculate N! If we can find a base case, we can write a recursive algorithm. Fortunately, we don't have to look too far: O! is defined in mathematics to be 1. |
|
|
|
|
|
|
|
|
IF n is O
Return 1
ELSE
Return n * Factorial(n - 1) |
|
|
|
|
|
|
|
|
|
This algorithm can be coded directly as follows. |
|
|
|
|
|
