Functional Python Programming

Recursions and Reductions

Following is an alternative which restates the entire algorithm to use stateful
variables instead of a simple recursion:

def fibi(n):

if n == 0: return 0

if n == 1: return 1

f_n2, f_n1 = 1, 1

for i in range(3, n+1):

f_n2, f_n1 = f_n1, f_n2+f_n1

return f_n1

Our stateful version of this function counts up from 0, unlike the

recursion, which counts down from the initial value of n. It saves the

values of Fn− 2 and Fn− 1 that will be used to compute Fn. This version is

considerably faster than the recursive version.

What's important here is that we couldn't trivially optimize the recursion with an
obvious rewrite. In order to replace the recursion with an imperative version, we
had to look closely at the algorithm to determine how many stateful intermediate
variables were required.

Processing collections via recursion

When working with a collection, we can also define the processing recursively.
We can, for example, define the map() function recursively. The formalism looks
as follows:

()

()[] ()()[]

()

()

[] 0

,

, : 1 1 0

C

mapfC

mapfC append fC C

 =

=

 − − ≠

if len

if len

We've defined the mapping of a function to an empty collection as an empty
sequence. We've also specified that applying a function to a collection can be
defined recursively with a three step expression. First, apply the function to all of
the collection except the last element, creating a sequence object. Then apply the
function to the last element. Finally, append the last calculation to the previously
built sequence.