递归(Recursion)

树形结构是自身重复的。树的每个孩子节点都是树，每个孩子节点的孩子节点也是树，以此类推。正如编程语言一样，树形结构也是递归和重复的。显然，如果我们想编写函数处理所有可能的情况，就必须要保证函数可以处理任意深度。幸运的是，我们可以使用递归函数的天生优势来轻松地处理这种重复自身的结构。

简而言之，递归函数就是在执行的过程中调用自身的函数。这听起来可能有些奇怪，因为这会导致函数无穷尽地执行下去。但是函数对于不同的输入会产生不同的输出，如果我们每次递归都改变或使用不同的输入，并设置递归终止的条件，我们就可以使用递归做一些有用的事情。

举个例子，我们可以使用递归来计算树形结构中节点个数。

首先考虑最简单的情况，如果输入的树没有子节点，我们只需简单的返回 1 就行了。如果输入的树有一个或多个子节点，这时返回的结果就是自身节点的 1，加上所有子节点的值。

但我们怎样得到所有子节点的值呢？这正是我们要着手解决的问题。请看下面的 C 语言代码。

int number_of_nodes(mpc_ast_t* t) {
  if (t->children_num == 0) { return 1; }
  if (t->children_num >= 1) {
    int total = 1;
    for (int i = 0; i < t->children_num; i++) {
      total = total + number_of_nodes(t->children[i]);
    }
    return total;
  }
}

递归函数的定义可能看起来有些奇怪。我们首先假定存在某个函数能够正确的工作，然后使用它来编写刚刚假定存在的函数。

正如世间万物，递归函数也有规律可循。首先需要定义的是最基本的情况，用来终止递归的执行。例如上例中的 t->children_num == 0。之后定义的是需要递归的情况，例如上例中的 t->children_num >= 1。这部分将计算过程分为几个相似的部分，然后调用自身来递归处理这些部分，最后将结果整合起来。

理解递归函数需要动一番脑筋，在继续之前，请确保自己理解了上面的内容。在后面的章节中，我们会大量地用到递归。如果你还是不清楚递归的原理，请参考本章福利部分的某些问题。