Scala 中的匿名递归函数

Question

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

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

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

Answer 1

正如您发布的链接中所述。您可以使用 Y 组合器。这是示例：

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 组合器的调用到一个普通的、惯用的递归调用（当然，带有尾调用优化）。这个想法是，像这样的调用

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...

Answer 5

Scala 上的递归调用。
让我以 N 个数字之和为例进行递归

var sumIt:(Int => Int) = (x: Int) => {if(x<=1) 1 else sumIt(x-1)+x}


 scala> sumIt(10) 
val res141: Int = 55

您可以看到 sumIt 的类型为 Int，Int 作为输入和返回值。 sumIt lambda 函数采用 Integer 作为参数，并对 sumIt 进行递归调用。

我只是为了方便理解递归调用而举这个例子。您可以直接计算此逻辑的公式，例如...

sumValue = (N*(N+1)) /2

Answer 6

添加到 @in-ho-yi 的答案。为简单起见，您可以直接在匿名函数内部定义本地函数并将其用于递归。另外，在本地函数之前使用 @tailrec 可以确保它将应用尾递归，而 Y 组合器无法做到这一点。

这是比 Y-combinator 更好的方法，因为它只向堆栈添加 2 帧，并且每次调用函数时添加 1 帧（如果不是尾递归，则总共只会添加 1 帧，因此最多将使用 3 帧）而不是 Y-combinator 使用的每次调用 6 个

import scala.annotation.tailrec

val fact = {(input: BigInt)=>
  @tailrec
  def f(x:BigInt, acc: BigInt = 1):BigInt = {
    if(x<=1) acc
    else f(x-1, x*acc)
  }
  f(input)
}

print(fact(1024))

Answer 7

一个非常简单的方法：

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

// Use as anonymous function below
(1 to 5).map { (x: Int) =>
  def f(x: Int): Int = if (x == 0) 1 else x * f(x-1)
  f(x)
}

// res0: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 6, 24, 120)