Functional Python Programming - Third Edition

 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 ...