Scala中的递归(译)

May 18, 2012

声明:本文翻译自这里

###递归101
我们都知道什么是递归吧?一个自己调用自己的函数,或者函数A调用函数B,函数B又调用函数A,或者是A调用B,B调用C, C调用A。但是我们大多数情况下所说的递归函数,是指一个调用自身的函数。
在Java世界中,递归函数的曝光率很低,说起来有不少原因。
第一,递归不直观,难以理解。对于一段循环代码(for, while), 你可以很直白地看到这段逻辑的全景,即便你是一个初学者,而对于一段递归代码,就不是那么容易了,你只能看到递归逻辑的一次调用,而不得不想象当递归调用发生时,这些多次调用是如何组合在一起的。
第二,比起递归,循环在java中更加容易实现,比如for ,for-each,while, do-while, 数组, iterator, ResultSet,这些结构都是用来实现循环的。
第三,Java中的递归有自己的Achille’s heel: call stack。

总的来说,当调用一个函数时,一个新的call stack frame会被放到call stack的顶部,用以保存局部变量,当前函数的caller,等等。但是,call stack的大小是有限的,当递归的深度不是很深时,调用递归函数是没有什么问题的,但是如果递归调用的深度无法预计,那么很有可能会导致stack overflow. 而循环却不会有这种问题(因为循环不会产生新的call stack frame),因此,使用循环更加安全。

###Scala中的递归
Scala,作为一新兴的functional language,更偏爱递归胜过循环,那么在scala中,是如何解决call stack大小限制的问题的呢?我们来看一个例子:

  def listLength1(list: List[_]): Int = {
    if (list == Nil) 0
    else 1 + listLength1(list.tail)
  }

  var list1 = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  var list2 = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  1 to 15 foreach( x => list2 = list2 ++ list2 )

  println( listLength1( list1 ) )
  println( listLength1( list2 ) )

函数listLenght1递归地计算list中item的数量,这个函数在计算item数量较少的list时工作地很好,然而在item数量很大时,就会得到stack overflow错误. 递归是函数式语言的谋生手段,但是在Scala中,递归仍然倒在了stack overflow的脚下。

先别急着放弃,Scala有一个很重要的优化递归的方案,只要你用了正确的递归类型。

###首递归和尾递归 根据递归调用的方式,递归可以分为首递归和尾递归。在首递归函数中,函数调用自身后,再进行其他运算(可能会把自用自身后的结果做为这些运算的输入)。在尾递归函数中,所有的计算都在函数调用自身前完成,调用自身是尾递归函数中做的最后一件事情。

这两种递归的区别的重要性目前看起来还不是那么明显,然而,它确实很重要!想象一下一个尾递归函数的执行过程,首先完成所有的计算,在最后一步,马上进行对自身递归的调用,一般情况下,这个时候就该使用call stack frame记录方法调用状态了,然而,这里却不需要:我们不需要记录局部变量,因为所有的计算都已经完成。我们也不需要知道目前在哪个函数中,因为我们始终在同一个函数中。基于以上前提,scala不会创建一个新的call stack frame,而是重用当前的call stack frame ,无论调用次数有多少,call stack也不会增长。这就是scala中尾递归函数的特殊性。在其他语言中,语言设计者通过把尾递归转换成循环的方式进行了优化。

而在首递归函数中,递归调用是不一样的,这是为什么呢?想象一下一个首递归函数的执行过程:先执行一些计算,在递归调用自身,然后在执行另一些计算。在调用自身前,需要记住当前的局部变量,以便在从递归调用返回后继续进行后面的运算,这样,就必须创建一个新的call stack frame来记录当前状态。因此首递归函数还是会有stack overflow的风险。并且无法被优化。

在这里问你一个问题,上面的listLenght1是一个尾递归还是首递归?让我们来看着这个函数做了哪些事情。
A) 检查参数是否为Nil。
B) 如果为空,返回零,因为Nil的长度是零。
C) 如果不为空,则返回1加上递归调用的结果。
递归调用逻辑在这个函数的最后一行,应该是尾递归函数吧?错!在尾递归调用结束后,然后对递归调用结果加一,然后返回最终结果。这实际上首递归(或者可以叫做中递归)因为递归调用并不是所有运算的最后一步。

###尾递归例子
当你用scala写一个递归函数时,你的目标是写成尾递归以便编译器对尾递归进行优化。现在让我们把上面的那个函数重写为尾递归函数。

def listLength2(list: List[_]): Int = {
  def listLength2Helper(list: List[_], len: Int): Int = {
    if (list == Nil) len
    else listLength2Helper(list.tail, len + 1)
  }
  listLength2Helper(list, 0)
}

println( listLength2( list1 ) )
println( listLength2( list2 ) )

我写成两个函数(listLength2 和一个内部的helper函数)以便和上面的例子中的函数接口保持一致。如果你能给listLength2Helper的参数给个默认值,我们就能只提供一个函数,但是我不知道怎么做。长话短说:listLength2只调用了做了实际工作的listLength2Helper,而且listLength2Helper也是个递归函数。

listLength2Helper是个尾递归函数吗?递归调用是所有运算的最后一步,允许scala进行优化?就像listLenght1一样,listLength2首先检查参数是否为Nil,如果不是,就进行递归调用,但是仍然会有一个加一的操作 —— len + 1。难道这个就不是尾递归吗?不,len + 1 运算会在递归调用前运算。只有所有的参数运算完了以后,才会进行递归调用,这个函数确实是个尾递归函数。

readable angular tests

In this post, I'll provdes some tips to create readable angular test.### General Tips#### Use describe or nested describe to structure sp...… Continue reading

Exposing event stream from monolith

Published on September 18, 2017