This page intentionally left blank Python for Software Design
tải về 1.38 Mb. Chế độ xem pdf
|
| frabjous: An adjective used to describe something that is frabjous.
If you saw that definition in the dictionary, you might be annoyed. On the other hand, if you looked up the definition of the factorial function, denoted with the symbol !, you might get something like this: 0 ! = 1 n ! = n(n − 1)! This definition says that the factorial of 0 is 1, and the factorial of any other value, n, is n multiplied by the factorial of n − 1. So 3 ! is 3 times 2!, which is 2 times 1!, which is 1 times 0!. Putting it all together, 3! equals 3 times 2 times 1 times 1, which is 6. If you can write a recursive definition of something, you can usually write a Python program to evaluate it. The first step is to decide what the parameters should be. In this case it should be clear that factorial takes an integer: def factorial(n): If the argument happens to be 0, all we have to do is return 1: def factorial(n): if n == 0: return 1 66 Fruitful Functions Otherwise, and this is the interesting part, we have to make a recursive call to find the factorial of n − 1 and then multiply it by n: def factorial(n): if n == 0: return 1 else: recurse = factorial(n-1) result = n * recurse return result The flow of execution for this program is similar to the flow of countdown in Section 5.8. If we call factorial with the value 3: Since 3 is not 0, we take the second branch and calculate the factorial of n - 1 . . . Since 2 is not 0, we take the second branch and calculate the factorial of n - 1 . . . Since 1 is not 0, we take the second branch and calculate the factorial of n - 1 . . . Since 0 is 0, we take the first branch and return 1 without making any more recursive calls. The return value (1) is multiplied by n, which is 1, and the result is returned. The return value (1) is multiplied by n, which is 2, and the result is returned. The return value (2) is multiplied by n, which is 3, and the result, 6, becomes the return value of the function call that started the whole process. Here is what the stack diagram looks like for this sequence of function calls: n 3 recurse 2 recurse 1 recurse 1 __main__ factorial n 2 n 1 n 0 factorial factorial factorial 1 1 2 6 1 result 2 6 result result The return values are shown being passed back up the stack. In each frame, the return value is the value of result, which is the product of n and recurse. In the last frame, the local variables recurse and result do not exist, because the branch that creates them does not execute. 6.7 One More Example 67 6.6 LEAP OF FAITH Following the flow of execution is one way to read programs, but it can quickly become labyrinthine. An alternative is what I call the “leap of faith.” When you come to a function call, instead of following the flow of execution, you assume that the function works correctly and returns the right result. In fact, you are already practicing this leap of faith when you use built-in functions. When you call math.cos or math.exp, you don’t examine the bodies of those func- tions. You just assume that they work because the people who wrote the built-in functions were good programmers. The same is true when you call one of your own functions. For example, in Section 6.4, we wrote a function called is_divisible that determines whether one number is divisible by another. Once we have convinced ourselves that this function is correct – by examining the code and testing – we can use the function without looking at the body again. The same is true of recursive programs. When you get to the recursive call, instead of following the flow of execution, you should assume that the recursive call works (yields the correct result) and then ask yourself, “Assuming that I can find the fac- torial of n − 1, can I compute the factorial of n?” In this case, it is clear that you can, by multiplying by n. Of course, it’s a bit strange to assume that the function works correctly when you haven’t finished writing it, but that’s why it’s called a leap of faith! 6.7 ONE MORE EXAMPLE After factorial, the most common example of a recursively defined mathematical function is fibonacci, which has the following definition: ∗ fibonacci tải về 1.38 Mb. Chia sẻ với bạn bè của bạn:
|