# 2.3. Functional Programming - Recurring On Lists That Aren't Flat¶

## 2.3.1. Deep Recursion in FP (1)¶

In the previous section, we limited our treatment of list-processing
functions to operating on *flat* lists of integers, that is, list that
do not themselves contain nested inner lists. In this section, we
will consider how to operate on lists that can contain not only
integers, but also lists. This will lead to a discussion of "deep
recursion," which can handle trees represented as lists of lists of ... lists of integers nested arbitrarily deep.

A good guideline for deep recursion is the following. When recurring
on a list of creatures *lst* that may themselves be lists, recur on both
*fp.hd(lst)* and *fp.tl(lst)* – just make sure *lst* is not empty and
that *fp.hd(lst)* is a list.

Consider the following **tree_test** list as an example:

```
var tree_test = [14, [7, [], [12, [], []]],
[26, [20, [17, [], []],
[] ],
[31, [], []]]]
```

We want to develop a function that takes in an integer tree represented as a list of lists of …lists of integers and returns the sum of the integers in the tree.

```
var sumTree = function (ns) {
if (fp.isNull(ns)) {
return 0;
} else if (???????) {
return ?????????;
} else {
return ?????????;
}
}
```

Once you have decided how to fill in the **???????** in the preceding
example, consider the slight modification in the following review
problem.

## 2.3.2. Deep Recursion 2¶

Notice that our **tree_test** is actually a binary search tree under
the interpretation that the first nested list following a number is
the left subtree of that number and the second nested list following a
number is the right subtree. Using this represented of the tree,
write a function **path**

**var path = function (n, bst)**

where **n** is a
number and **bst** is a binary search tree that contains the number
*n*. **path** should return a list of 0’s and 1’s showing how to find
the node containing **n**, where 1 indicates "go right" and 0 indicates
"go left". If *n* is found at the root, the empty list is
returned. Example usage:

```
> var tree_test = [14, [7, [], [12, [], []]],
[26, [20, [17, [], []],
[] ],
[31, [], []]]]
> path(17, tree_test)
[1, 0, 0]
```

In writing this function, you should be using **cons** to construct the returned list as you progress through the tree using a deep recursion strategy. Once you feel you have a correct solution, use similar logic in developing a solution for the following review problem.

This problem again deals with deep recursion and more specifically with the
`subst`

function that was previously described.

## 2.3.3. Deep Recursion 3¶

This problem is similar to (and assumes that you have solved) the previous problem.

## 2.3.4. Deep Recursion 4¶

As a final example to give you a lot more practice with deep recursion, consider the following randomized exercise. You have to solve it correctly three times in a row.