3.1. FP 中的深层递归¶

在上一个章节中，我们将列表处理函数的处理范围限制在操作 flat 整数列表上，即本身不包含嵌套内部列表的列表。在本章节中，我们将考虑如何操作不仅包含整数，还包含列表的列表。这将导致对 deep recursion 的讨论，它可以处理以列表的列表的... 列表的整数嵌套表示的树。

深度递归的一个良好指导原则如下。

考虑以下 tree_test 列表作为例子:

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

我们希望开发一个函数，该函数接受一个以整数列表的列表...列表的列表表示的整数树作为输入，并返回树中整数的总和。

Settings

Saving...
Server Error
Resubmit

既然我们在前面的幻灯片演示中已经看到了一个深层递归的例子，现在考虑下面复习问题中的微小修改。

3.2. 二叉搜索树上的深度递归¶

注意，虽然我们的 sumTree 函数可以作用于任意嵌套列表，但我们特定的 tree_test 示例实际上是一个二叉搜索树，其解释方式是：给定数字之后的第一个嵌套列表是该数字的左子树，其中只包含小于或等于该数字的值，而给定数字之后的第二个嵌套列表是该数字的右子树，其中只包含大于该给定数字的数字。 使用这种树的表示法，我们可以开发以下辅助函数，以处理那些是二叉搜索树的嵌套列表。

// Return the left subtree
var left = function (bst) {
   return fp.hd(fp.tl(bst));
};

// Return the right subtree
var right = function (bst) {
   return fp.hd(fp.tl(fp.tl(bst)));
};

// Is this tree a leaf node?
var isLeaf = function (tree) {
  return fp.isNull(left(tree)) && fp.isNull(right(tree));
};

使用这些辅助函数，我们可以轻松编写一个函数 path （下面将提到一个例外情况）

var path = function (n, bst) { ... };

其中 n 是一个数字， bst 是一棵包含数字 n 的二叉搜索树。 path 应该返回一个由 0 和 1 组成的列表，表示如何找到包含 n 的节点，其中 1 表示“向右走”，0 表示“向左走”。如果 n 在根节点处找到，则返回空列表。使用示例:

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

> path(17, tree_test) [1, 0, 0]

我们开发的函数有一个需要注意的地方，即当 n 不在树中时，它无法返回某种错误信号。我们将在 section on continuation passing style 中解决这一不足。

Settings

Saving...
Server Error
Resubmit

现在我们已经看到如何结合从深层递归返回的列表使用 cons，请考虑以下复习问题。它同样涉及深层递归，更具体地涉及在 递归线性表处理示例：subst( new, old, list ) 中描述的 subst 函数。

3.3. 使用深度递归进行练习¶

该问题与（并假设你已经解决了）前一个问题相似。

3.4. 更多关于深度递归的练习¶

作为最后一个例子，并且为了让您有更多的深度递归练习机会，请考虑以下随机练习。您必须连续三次正确解决它。