Recursions and Reductions

In previous chapters, we've looked at several related kinds of processing designs;
some of them are as follows:

• Mapping and filtering that 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 are several specialized
reduction functions, which include min(), max(), len(), and sum(). There's a
general-purpose reduction function, also, functools.reduce().

We'll also consider a collections.Counter() function as a kind of reduction
operator. It doesn't produce a single scalar value per se, but it does create a new
organization of the data that eliminates some of the original structure. At its heart,
it's a kind of count-group-by operation that has more in common with a counting
reduction than with a mapping.

In this chapter, we'll look at reduction functions in more detail. From a purely
functional perspective, a reduction is defined recursively. For this reason, we'll look
at recursion first before we look at reduction algorithms.

Generally, a functional programming language compiler will optimize a recursive
function to transform a call in the tail of the function to a loop. This will dramatically
improve performance. From a Python perspective, pure recursion is limited, so we
must do the tail-call optimization manually. The tail-call optimization technique
available in Python is to use an explicit for loop.

We'll look at a number of reduction algorithms including sum(), count(), max(),
and min(). We'll also look at the collections.Counter() function and related
groupby() reductions. We'll also look at how parsing (and lexical scanning) are
proper reductions since they transform sequences of tokens (or sequences of
characters) into higher-order collections with more complex properties.