Erlang极简学习笔记<05>——递归篇

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

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

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

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

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

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

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

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

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

  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会避免存储栈帧。因此，尾递归也适用于多个函数的情况

  a() -> b().
  b() -> c().
  c() -> a().
  

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

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

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

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

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

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

原文地址