Which the product and recurse that the last frame
| 5.6 Leap of faith | 55 |
|---|
Here is what the stack diagram looks like for this sequence of function calls:
| factorial | n | 3 | 2 | 6 | 6 | ||
|---|---|---|---|---|---|---|---|
| factorial | n | 2 | 1 |
|
2 | 2 | |
| factorial | n | 1 |
|
1 | 1 | 1 | |
| factorial | n | 0 | 1 |
Following the flow of execution is one way to read programs, but it can quickly become labyrinthine. An alternative is what we 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 appropriate value.
In fact, you are already practicing this leap of faith when you use built-in func-tions. When you call math.cos or math.exp, you don’t examine the implemen-tations of those functions. You just assume that they work because the people who wrote the built-in libraries were good programmers.
| 56 | Fruitful functions |
|---|---|
| call works (yields the correct result) and then ask yourself, “Assuming that I can find the factorial of n − 1, can I compute the factorial of n?” In this case, it is clear that you can, by multiplying by n. | |
In the previous example, we used temporary variables to spell out the steps and to make the code easier to debug, but we could have saved a few lines:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
fibonacci(n) = fibonacci(n − 1) + fibonacci(n − 2);
Translated into Python, it looks like this:
