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

  • 递归的定义就是:调用自己的函数。不过仅仅让函数调用自己还不够,我们还需要一个终止条件,又称为基本情形(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)函数