6
Recursions and Reductions
Many functional programming language compilers will optimize a recursive function to transform a recursive call in the tail of the function to an iteration. This tail-call optimization will dramatically improve performance. Python doesn’t do this automatic tail-call optimization. One consequence is pure recursion suffers from limitations. Lacking an automated optimization, we need to do the tail-call optimization manually. This means rewriting recursion to use an explicit iteration. There are two common ways to do this, and we’ll consider them both in this chapter.
In previous chapters, we’ve looked at several related kinds of processing design patterns; some of them are as follows:
Mapping and filtering, which create collections from collections
Reductions that create a scalar value from a collection
The distinction is exemplified by functions such as map() and filter() that accomplish the first kind of collection processing. There...
