如何编写递归匿名函数？

Question

在我继续学习scala的过程中，我正在阅读Odersky的《Scala by example》一书，并在第一类函数章节中工作。匿名函数部分避免了递归匿名函数的情况。我有一个看起来可行的解决方案，但我很好奇是否有更好的答案。从pdf中可以看到，这是展示高阶函数的代码。

def sum(f: Int => Int, a: Int, b: Int): Int =
  if (a > b) 0 else f(a) + sum(f, a + 1, b)

def id(x: Int): Int = x
def square(x: Int): Int = x * x
def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x-1)

def sumInts(a: Int, b: Int): Int = sum(id, a, b)
def sumSquares(a: Int, b: Int): Int = sum(square, a, b)
def sumPowersOfTwo(a: Int, b: Int): Int = sum(powerOfTwo, a, b)

scala> sumPowersOfTwo(2,3)
res0: Int = 12

从PDF中： 展示匿名函数的代码

def sum(f: Int => Int, a: Int, b: Int): Int =
  if (a > b) 0 else f(a) + sum(f, a + 1, b)

def sumInts(a: Int, b: Int): Int = sum((x: Int) => x, a, b)
def sumSquares(a: Int, b: Int): Int = sum((x: Int) => x * x, a, b)
// no sumPowersOfTwo

我的代码：

def sumPowersOfTwo(a: Int, b: Int): Int = sum((x: Int) => {
   def f(y:Int):Int = if (y==0) 1 else 2 * f(y-1); f(x) }, a, b)

scala> sumPowersOfTwo(2,3)
res0: Int = 12

- James T Kirk

---

你确定吗？echo "2^2+3^2" | bc -l --> 13。 - sarnold

这是一个重复的问题 https://dev59.com/RW435IYBdhLWcg3wkBBe。 - Suroot

@sarnold 二的幂次方之和 - 即 2^a + 2^a+1 + .... 2^b-1 + 2^b 2^2+2^3 = 4+8 = 12 - James T Kirk

@James，啊。我会低头羞愧地离开评论区，希望这条评论能帮助其他人避免同样的尴尬。 - sarnold

我不理解这些函数中的“匿名”是什么意思。 - user unknown

Answer 1

就算是这样...（标题和“真正的问题”并不完全一致）

可以通过“长手写法”扩展FunctionN，然后在apply内部使用this(...)来创建递归匿名函数对象。

(new Function1[Int,Unit] {
  def apply(x: Int) {
    println("" + x)
    if (x > 1) this(x - 1)
  }
})(10)

然而，这通常引入的不适宜性使得这种方法通常不是最理想的。最好只使用一个“名称”，并具有一些更具描述性和模块化的代码--尽管以下内容并不是这样做的非常好的论据；-）

val printingCounter: (Int) => Unit = (x: Int) => {
    println("" + x)
    if (x > 1) printingCounter(x - 1)
}
printingCounter(10)

编程愉快。

- user166390

Answer 2

您可以将这种间接递归泛化为：

case class Rec[I, O](fn : (I => O, I) => O) extends (I => O) {
  def apply(v : I) = fn(this, v)
}

现在，可以使用间接递归来编写总和，如下所示：

val sum = Rec[Int, Int]((f, v) => if (v == 0) 0 else v + f(v - 1))

同样的解决方案可以用来实现记忆化，例如。

- Jesper Nordenberg