• 函数式编程语言中通常没有类似 for 和 while 这样的循环结构

  • 递归的定义就是：调用自己的函数。不过仅仅让函数调用自己还不够，我们还需要一个终止条件，又称为基本情形(base case)

  • 利用递归实现一个计算列表长度的函数

    1
    2
    len([]) -> 0;
    len([_|T]) -> 1 + len(T).

  • 尾递归可以把线性过程转换成迭代过程

  • 要让一个函数变成尾递归，这个函数必须是“孤立的”

  • 尾递归不会引起内存消耗的增长，当一个函数在尾部(函数中最后一个被求值的表达式)调用了自身，就称为尾递归优化(tail recursion optimization, TRO)

  • 为了实现尾递归优化，需要给函数增加一个额外的临时变量参数，这个临时变量参数又称为累加器(accumulator)

  • 为了限制调用链的增长，需要在调用发生时就把结果计算出来，累加器就是用来保存这个计算结果的

    1
    2
    3
    fac(N) -> fac(N, 1).
    fac(0, Acc) -> Acc;
    fac(N, Acc) when N > 0 -> fac(N-1, N*Acc).

  • 注意：Erlang中不允许在函数中使用默认参数

  • 形象点说，尾递归就是：给函数增加一个参数，把那个计算的部分放到函数调用中去

  • 递归是Erlang中仅有的循环结构(列表推导式除外)

  • 尾递归优化是一个更为一般的优化方法的特例，这种更为一般的优化方法称为尾调用优化(last call optimization, LCO)

  • 当函数体中的最后一个被求值的表达式是另一个函数调用时，就会进行LCO

  • 在进行LCO时，和TRO一样，Erlang VM会避免存储栈帧。因此，尾递归也适用于多个函数的情况

    1
    2
    3
    a() -> b().
    b() -> c().
    c() -> a().

  • 上面的函数调用链实际上导致了一个无限循环，但不会耗尽内存，因为LCO避免了栈溢出。这条原则，再加上累加器的使用，成就了尾递归的可用性

  • 递归与其它命令式语言中对应物相比（通常是 while 或者 for 循环），一个不同之处在于，它不是采用逐步执行的方式（先做这个，然后做那个，再做这个，最后完成），递归方法是更加声明性的（如果输入是这个，这么做，否则，那么做）。借助于函数头中的模式匹配，这个区别就变得更加明显

  • 递归加上模式匹配，往往是编写简洁、易读算法的最佳选择。把问题的每个部分都分解到不同的函数中，直到不能再被简化为止

  • 从更漂亮和易理解的普通递归开始，再到理论上更加高效的尾递归，是个全面学习的好方法

  • 在实践中，你会发现尾递归和普通递归在性能上的差别很小

  • 那些会永远循环的函数需要小心对待，例如主循环。还有一些类型的函数，如果不把它们改成尾递归的形式，就会产生非常大的调用栈，会变慢，还可能会早早崩溃，例如斐波那契(Fibonacci)函数