递归函数

引入条件分支，实际上让我们的语言变得更加强大。 因为条件分支可以有效地让我们实现递归函数。

递归函数是那些自己调用自己的函数。 我们已经在C中使用这些来执行表达式的读取和求值。 我们需要条件分支的原因是因为它们让我们检验我们想要终止递归的情况。

例如，我们可以使用条件分支来实现一个函数len，该函数返回列表中元素个数。 如果我们遇到空列表，我们只返回0。 否则我们返回输入列表的tail的长度加上1。 想想为什么会这样。 它重复调用len函数，直到遇到空列表。 此时它返回0并将所有其他部分结果加在一起。

(fun {len l} {
  if (== l {})
    {0}
    {+ 1 (len (tail l))}
})

就像在C中一样，递归函数具有令人愉悦的对称性。 首先，我们对空列表（基线条件）做一些处理。 然后，如果我们得到更大的列表，我们就会取出一个部分，例如列表的头部元素，并对它做一些处理，然后再将它与已经调用了该函数的其余部分进行组合。

这是另一个递归函数——反转列表。 和之前一样，函数检查列表是否空列表，但该函数中基线条件的处理是返回空列表。这是合理的，因为空列表的反转形式同样也是空列表。 但如果是更大的列表，函数会使尾部反转，并将其放在头部前面。

(fun {reverse l} {
  if (== l {})
    {{}}
    {join (reverse (tail l)) (head l)}
})

我们将使用递归来构建许多函数。 因为这将成为在我们的语言中实现循环的主要方式。