not linear (nor polynomial), but also not completely nonlinear - it is a rational difference equation) So after a full day of searching, I found the answer and hopefully these findings will be of help to others. ![]() ![]() 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.Ok, I know you didn't want generating functions (GF from now on) and all the complicated stuff, but my problem turned out to be nonlinear and simple linear methods didn't seem to work. 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. 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. 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. The termination condition is the most important part of a recursive definition. In the case of power, the termination condition (given in the test clause of the definition) is that the second argument is 0. In principle there is no limit to how deep recursion can go.Īny recursive function will cause a stack overflow if it does not have a proper termination condition. 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. 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. Eventually the first call to power (the ``top-level'' call) is able to finish its multiplication, the result is 81.Įach time power is called recursively, a new level of recursion is created. 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. 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. 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. 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. Obviously, this multiplication cannot be completed without first calculating (power 3 3). There is a corresponding function 1+.) This is the same, then, as (* 3 (power 3 3)). 1- is a function that decrements its argument by 1. Since y is not equal to zero, the expression (* x (power x (1- y))) is evaluated. When (power 3 4) is evaluated, the local variables x and y are set to 3 and 4 respectively. Now enter the following expression at the interpreter's prompt:Īll well and good. Use an editor to enter the definition of power given above and evaluate it in the LISP interpreter. (As always, we assume that you have a machine running LISP in front of you, and that you experiment with the examples we give.) 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. ![]() The else clause of the if statement in this definition contains a reference to power. For example, look at this definition of a function to calculate x to the power of y (for positive integer values of y): The distinctive feature of a recursive function is that, when called, it may result in more calls to itself. ![]() Next: Using Trace To Up: Recursive Definitions Previous: Recursive Definitions
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |