The distinctive feature of a recursive function is that, when called, it may result in more calls to itself. For example, look at this definition of a function to calculate x to the power of y (for positive integer values of y):
(defun power (x y)
(if (= y 0) 1
(* x (power x (1- y)))))
The else clause of the if statement in this definition contains a reference to power. How can a function make use of itself in its own definition? To understand this, let's examine how power works when it is called. (As always, we assume that you have a machine running Lisp in front of you, and that you experiment with the examples we give.)
Use an editor to enter the definition of power given above and evaluate it in the Lisp interpreter. Now enter the following expression at the interpreter's prompt:
All well and good. Here is what happened. When (power 3 4) is evaluated, the local variables x and y are set to 3 and 4 respectively. Then the if statement is evaluated. Since y is not equal to zero, the expression (* x (power x (1- y))) is evaluated. 1- is a function that decrements its argument by 1. There is a corresponding function 1+.) This is the same, then, as (* 3 (power 3 3)). Obviously, this multiplication cannot be completed without first calculating (power 3 3). So, another call to power is made. This time, x and y are both 3. It is important to realize that these new values of x and y are local only to the second call to power -- the previous call knows nothing about them, and neither will any subsequent call. As before, the test clause of the if statement is false, so the expression (* 3 (power 3 2)) needs to be evaluated, which results in a third call to power with x equal to 3 and y equal to 2. The fifth time that power gets called, its arguments are 3 and 0; this time the test clause is true, so (power 3 0) returns 1 and the recursion stops. Now the previous call to power (the fourth one) is able to complete the multiplication (* 3 (power 3 0)) and returns 3 to the next level up, and so on. Eventually the first call to power (the ``top-level'' call) is able to finish its multiplication, the result is 81.> (power 3 4) 81
Each time power is called recursively, a new level of recursion is created. Is there a limit to how deep the recursion can go? The answer is yes, but how deep this limit is, and how easy it is to change it, will depend on the particular version of Lisp you are using. If you exceed the limit, you will see an error message saying something like ``Function call stack overflow.'' This limit is a practical limit imposed by hardware limitations and details of the specific implementation of Lisp you are using. In principle there is no limit to how deep recursion can go.
Any recursive function will cause a stack overflow if it does not have a proper termination condition. In the case of power, the termination condition (given in the test clause of the definition) is that the second argument is 0. The termination condition is the most important part of a recursive definition. You want to make sure your program will terminate! Were it not for the stack overflow, a bad terminate condition would result in an infinite spiral.
Think too, what would happen if you called this version of power with y as a negative number or a non-integer as the second argument. This shortcoming of power does not make it a ``robust'' piece of programming, since it is not always safe to assume that whoever uses power will be careful not to make y negative or an integer. A robust power function would do something appropriate with negative or non-integer second arguments, like provide the correct answer! (Or, at least provide an informative error message.)
© Colin Allen & Maneesh Dhagat