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

Many forms of recursion rely on a tail call. In fact, the first example in the previous section does. A tail call occurs any time the recursion makes a call to the function as the last thing before it returns. In the previous section, the line return n * factorial(n-1) is the tail call.

Tail calls aren’t necessarily bad, and they represent the manner in which most people write recursive routines. However, using a tail call forces Python to keep track of the individual call values until the recursion rewinds. Each call consumes memory. At some point, the system will run out of memory and the call will fail, causing your algorithm to fail as well. Given the complexity and huge datasets used by some algorithms today, tail calls can cause considerable woe to anyone using them.

With a little fancy programming, you can potentially eliminate tail calls from your recursive routines. You can find a host of truly amazing techniques online, such as the use of a trampoline, as explained at https://blog.moertel.com/posts/2013-06-12-recursion-to-iteration-4-trampolines.html. (Mind you, this isn’t the sort of trampoline you jump on at home!) However, the simplest approach to take when you want to eliminate recursion is to create an iterative alternative that performs the same task. For example, here is a factorial() function that uses iteration instead of recursion to eliminate the potential for memory issues:

def factorial(n): print("factorial called with n = ", str(n)) result = 1 while n > 1: result = result * n n = n - 1 print("Current value of n is ", str(n)) print("Ending condition met.") return result print(factorial(5))

The output looks very similar to before:

factorial called with n = 5Current value of n is 4Current value of n is 3Current value of n is 2Current value of n is 1Ending condition met.120

The basic flow of this function is the same as the recursive function. A while loop replaces the recursive call, but you still need to check for the same condition and continue looping until the data meets the condition. The result is the same. However, replacing recursion with iteration is nontrivial in some cases, as explored in the example at https://blog.moertel.com/posts/2013-06-03-recursion-to-iteration-3.html.