# Chapter 3: Functional Programming

## 3.1 Recursion

"It always takes longer than you expect, even when you take into account Hofstadter's Law." - *Hofstadter's Law*

Defining solution of a problem in terms of the same problem, typically of smaller size, is called recursion. Recursion makes it possible to express solution of a problem very concisely and elegantly.

A function is called recursive if it makes call to itself. Typically, a recursive function will have a terminating condition and one or more recursive calls to itself.

### 3.1.1 Example: Computing Power

Mathematically we can define power of a number in terms of its smaller power.

```
def power(x, n):
"""
Computes the result of x raised to the power of n.
>>> power(2, 3)
8
>>> power(3, 2)
9
"""
if n == 0:
return 1
else:
return x * power(x, n-1)
```

Number of calls to the above `power`

function is proportional to size of the problem, which is `n`

here. There are some recursive functions where the number of calls grow exponentially with the input size. The former kind of recursion is called linear recursion and the latter tree recursion.

**Problem 3.1.** The above implementation of `power`

function takes O(n) operations to compute the `power`

. It is possible to compute `power`

in O(ln(n)) operations. Can you provide an implementation for that?

**Problem 3.2.** Implement a function `add`

to add 2 numbers recursively using the following `increment`

and `decrement`

functions.

```
def increment(n): return n+1
def decrement(n): return n-1
```

### 3.1.2 Example: Flatten a list

Consider the problem where you have a nested list and want to flatten it.

```
def flatten_list(a):
"""Flattens a nested list.
>>> flatten_list([ [1, 2, [3, 4] ], [5, 6], 7])
[1, 2, 3, 4, 5, 6, 7]
"""
result = []
for x in a:
if isinstance(x, list):
result += flatten_list(x)
else:
result.append(x)
return result
```

**Problem 3.3.** Write a function `flatten_dict`

to flatten a nested dictionary by joining the keys with `.`

character.

```
>>> flatten_dict({'a': 1, 'b': {'x': 2, 'y': 3}, 'c': 4})
{'a': 1, 'b.x': 2, 'b.y': 3, 'c': 4}
```

**Problem 3.4.** Write a function `unflatten_dict`

to do reverse of `flatten_dict`

.

```
>>> unflatten_dict({'a': 1, 'b.x': 2, 'b.y': 3, 'c': 4})
{'a': 1, 'b': {'x': 2, 'y': 3}, 'c': 4}
```

**Problem 3.5.** Write a function `treemap`

to map a function over nested list.

```
>>> treemap(lambda x: x*x, [1, 2, [3, 4, [5] ] ])
[1, 4, [9, 16, [25] ] ]
```

**Problem 3.6.** Write a function `count_change`

to count the number of ways to change any given amount. Available coins are also passed as argument to the function.

```
>>> count_change(10, [1, 5])
3
>>> count_change(10, [1, 2])
6
>>> count_change(100, [1, 5, 10, 25, 50])
292
```

### 3.1.3 Example: Binary Trees

Binary tree is a hierarchical data structure in which every node contains a value and at most 2 children.

We need to choose a data structure to be able to perform operations on binary trees. However, we can assume functions to create node, access the children and value of a node to implement all the operations.

Let us assume that the following functions are available.

```
def leftchild(node):
"""Returns the left child of the given node.
If the left child is absent, None is returned.
"""
pass
def rightchild(node):
"""Returns the right child of the given node.
If the right child is absent, None is returned.
"""
pass
def getvalue(node):
"""Return the node value."""
pass
def makenode(value, left=None, right=None):
"""Creates a node with given value and left and right children.
>>> a = makenode(1, makenode(2), makenode(3))
>>> getvalue(a)
1
>>> getvalue(leftchild(a))
2
>>> getvalue(rightchild(a))
3
"""
pass
```

Now given these functions, we can write a module for doing operations on binary trees.

Lets start with a simple function to test whether a node is leaf.

```
def is_leaf(node):
"""Tests whether a node is leaf.
>>> a = make_node(1, make_node(2), None)
>>> is_leaf(a)
False
>>> is_leaf(leftchild(a))
True
"""
return leftchild(node) is None and rightchild(node) is None
```

The following function computes the leaf count of a tree.

```
def leafcount(root):
"""Computes number of leaf nodes in a binary tree.
>>> leafcount(make_node(1))
1
>>> leafcount(make_node(1, make_node(2), make_node(3)))
2
"""
if root is None:
return 0
elif is_leaf(root):
return 1
else:
return leafcount(leftchild(root)) + leafcount(rightchild(root))
```

**Problem 3.7.** Write a function `treeheight`

to compute height of a binary tree.

```
>>> treeheight(make_node(1))
1
>>> a = make_node(1, make_node(2), make_node(3, make_node(4), None))
>>> treeheight(a)
3
>>> treeheight(leftchild(a))
1
>>> treeheight(rightchild(a))
2
```

In-order traversal.

```
def inorder_traversal(root):
"""Returns values of all the nodes of a tree
in the order of inorder traversal."""
if root is None:
return []
else:
return inorder_traversal(leftchild(root)) + \
[getvalue(root)] + \
inorder_traversal(rightchild(root))
```

**Problem 3.8.** Write a function `preorder_traversal`

to return values of nodes in the order of preorder traversal.

**Problem 3.9.** Write a function `postorder_traversal`

to return values of nodes in the order of postorder traversal.

**Problem 3.10.** The above implementation of `inorder_traversal`

is very inefficient because it creates many temporary lists. Can you improve the performance of that function by appending values to a single list.

## 3.2 Higher Order Functions

In Python, functions are first-class objects. They can be passed as arguments to other functions and a new functions can be returned from a function call.

### 3.2.1 Example: Tracing Function Calls

For example, consider the following `fib`

function.

```
def fib(n):
if n is 0 or n is 1:
return 1
else:
return fib(n-1) + fib(n-2)
```

Suppose we want to trace all the calls to the `fib`

function.
We can write a higher order function to return a new function, which prints whenever `fib`

function is called.

```
def trace(f):
def g(x):
print f.__name__, x
value = f(x)
print 'return', repr(value)
return value
return g
fib = trace(fib)
print fib(3)
```

This produces the following output.

```
fib 3
fib 2
fib 1
return 1
fib 0
return 1
return 2
fib 1
return 1
return 3
3
```

To make the output more readable, let us indent the function calls.

```
def trace(f):
f.indent = 0
def g(x):
print '| ' * f.indent + '|--', f.__name__, x
f.indent += 1
value = f(x)
print '| ' * f.indent + '|--', 'return', repr(value)
f.indent -= 1
return value
return g
fib = trace(fib)
print fib(4)
```

It produces the following output.

```
$ python fib.py
|-- fib 4
| |-- fib 3
| | |-- fib 2
| | | |-- fib 1
| | | | |-- return 1
| | | |-- fib 0
| | | | |-- return 1
| | | |-- return 2
| | |-- fib 1
| | | |-- return 1
| | |-- return 3
| |-- fib 2
| | |-- fib 1
| | | |-- return 1
| | |-- fib 0
| | | |-- return 1
| | |-- return 2
| |-- return 5
5
```

### 3.2.2 Example: Memoize

In the above example, it is clear that number of function calls are growing exponentially with the size of input and there is lot of redundant computation that is done.

Suppose we want to get rid of the redundant computation by caching the result of `fib`

when it is called for the first time and reuse it when it is needed next time. Doing this is very popular in functional programming world and it is called `memoize`

.

```
def memoize(f):
cache = {}
def g(x):
if x not in cache:
cache[x] = f(x)
return cache[x]
return g
fib = trace(fib)
fib = memoize(fib)
print fib(4)
```

If you notice, after `memoize`

, growth of `fib`

has become linear.

```
|-- fib 4
| |-- fib 3
| | |-- fib 2
| | | |-- fib 1
| | | | |-- return 1
| | | |-- fib 0
| | | | |-- return 1
| | | |-- return 2
| | |-- return 3
| |-- return 5
5
```

**Problem 3.11.** Write a function `profile`

, which takes a function as argument and returns a new function, which behaves exactly similar to the given function, except that it prints the time consumed in executing it.

```
>>> fib = profile(fib)
>>> fib(20)
time taken: 0.1 sec
10946
```

## 3.3 exec and eval

Python is a dynamic language. It is possible to take a string and execute it as some python code.

For example:

```
>>> exec("x = 1")
>>> x
1
```

By default `exec`

works in the current environment, so it updated the globals in the above example.
It is also possible to specify an environment to `exec`

.

```
>>> env = {'a' : 42}
>>> exec('x = a+1', env)
>>> print env['x']
43
```

It is also possible to create functions or classes dynamically using `exec`

.

```
>>> code = 'def %s(): print "Hello %s"'
>>> for name in ['guido van rossum', 'linus torvalds', 'larry wall']:
... exec(code % (name.replace(' ', '_'), name.title()))
...
>>> guido_van_rossum()
Hello Guido Van Rossum
>>> linus_torvalds()
Hello Linus Torvalds
>>> larry_wall()
Hello Larry Wall
```

`eval`

is like `exec`

but it takes an expression and returns its value.

```
>>> eval("2+3")
5
>>> a = 2
>>> eval("a * a")
4
>>> env = {'x' : 42}
>>> eval('x+1', env)
43
```