Algorithms For Dummies

Eliminating tail call recursion

Many forms of recursion rely on a tail call. In fact, the 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 

http://blog.moertel.com/posts/2013- 

06-12-recursion-to-iteration-4-trampolines.html

.  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

 func-

tion that uses iteration instead of recursion to eliminate the potential for memory 

issues:

---

CHAPTER 5