Scala中的匿名递归函数

Question

有没有办法在Scala中编写一个递归的匿名函数？我在考虑这样的事情:

((t: Tree) => {
    print(t.value);
    for (c <- t.children)
        thisMethod(c)
})(root)

(相关问题:哪些语言支持*递归*函数文字/匿名函数？)

Answer 1

如您发布的链接中所述.你可以使用Y-combinator.这是一个例子:

scala> def fix[A,B](f: (A=>B)=>(A=>B)): A=>B = f(fix(f))(_)
fix: [A,B](f: ((A) => B) => (A) => B)(A) => B

scala> val fact = fix[Int,Int](f => a => if(a<=0) 1 else f(a-1) * a)
fact: (Int) => Int = <function1>

scala> fact(12)
res0: Int = 479001600

请注意,它不适用于大数字.小心尾调用优化.

Answer 2

如果你不想点击"惊人的数学",你可以回到scala的对象方面.

val fact = new Function1[Int,Int]{
    def apply(x:Int):Int = if(x==1) x else x * apply(x-1)
}

Answer 3

为了使它看起来更怪,你也可以使用这种代码风格:

val fact = new ((Int) => Int){
  def apply(x:Int):Int = if(x==1) x else x * apply(x-1)
}

Answer 4

在这个线程中添加了许多好的响应,Scala没有给我们尾调用优化定点组合器这一事实一直困扰着我,所以我决定编写一个宏来翻译类似Y-combinator的调用一个普通的,惯用的递归调用(当然,尾部调用优化).这个想法就像是一个电话

fix[Int,Int]((next) => (y) => ...body...)

很容易翻译成

({(input) =>
  object next {
    def apply(y:Int):Int = ...body...
  }
  next(input)
})

我已经将针对Scala 2.11的宏实现(稍微调整也应该与2.10一起使用)放到了这个要点中.

使用这个宏,我们可以匿名方式执行普通的递归任务,而不用担心堆栈溢出,例如

import asia.blip.ymacro.YMacro._
(y[BigInt,BigInt]((xx) => (y) => if(y==1) 1 else y * xx(y-1)))(2000)

给

res0: BigInt = 33162750924506332411753933805763240382811...