Читать книгу Algorithms For Dummies - John Paul Mueller, John Mueller Paul, Luca Massaron - Страница 93

Many people have a problem using recursion because they can’t easily visualize how it works. In most cases, you call a Python function, it does something, and then it stops. However, in recursion, you call a Python function, it does something, and then it calls itself repeatedly until the task reaches a specific condition — but all those previous calls are still active. The calls unwind themselves one at a time until the first call finally ends with the correct answer, and this unwinding process is where most people encounter a problem. Figure 4-1 shows how recursion looks when using a flow chart.

Notice the conditional in the center. To make recursion work, the function must have such a conditional or it could become an endless loop. The conditional determines one of two things:

 The conditions for ending recursion haven’t been met, so the function must call itself again.

 The conditions for ending recursion have been met, so the function returns a final value that is used to calculate the ending result.

FIGURE 4-1: In the recursion process, a function continuously calls itself until it meets a condition.

When a function calls itself, it doesn’t use the same arguments that were passed to it. If it continuously used the same arguments, the condition would never change and the recursion would never end. Consequently, recursion requires that subsequent calls to the function must change the call arguments in order to bring the function closer to an ending solution.

One of the most common examples of recursion for all programming languages is the calculation of a factorial. A factorial is the multiplication of a series of numbers between a starting point and an ending point in which each number in the series is one less than the number before it. For example, to calculate 5! (read as five factorial), you multiple 5 * 4 * 3 * 2 * 1. The calculation represents a perfect and simple example of recursion. Here’s the Python code you can use to perform the calculation.

def factorial(n): print("factorial called with n = ", str(n)) if n == 1 or n == 0: print("Ending condition met.") return 1 else: return n * factorial(n-1) print(factorial(5))

Here is the output you see when running this example:

factorial called with n = 5factorial called with n = 4factorial called with n = 3factorial called with n = 2factorial called with n = 1Ending condition met.120

The code meets the ending condition when n == 1. Each successive call to factorial() uses factorial(n-1), which reduces the starting argument by 1. The output shows each successive call to factorial and the meeting of the final condition. The result, 120, equals 5! (five factorial).

It's important to realize that there isn’t just one method for using recursion to solve a problem. As with any other programming technique, you can find all sorts of ways to accomplish the same thing. For example, here’s another version of the factorial recursion that uses fewer lines of code but effectively performs the same task:

def factorial(n): print("factorial called with n = ", str(n)) if n > 1: return n * factorial(n-1) print("Ending condition met.") return 1 print(factorial(5))

Note the difference. Instead of checking the ending condition, this version checks the continuation condition. As long as n is greater than 1, the code will continue to make recursive calls. Even though this code is shorter than the previous version, it's also less clear because now you must think about what condition will end the recursion.