Scala递归闭包编译错误

Question

我正在尝试实现一个memoized Fibonacci数字函数,我遇到了一个我无法解决的编译错误.以下代码是我到目前为止的代码.

var fibs = Map.empty[Int, Int]
fibs += 0 -> 1
fibs += 1 -> 1
fibs += 2 -> 2
val fib = (n: Int) => {
  if (fibs.contains(n)) return fibs.apply(n)
  else{
    // Error here
    val result = fib(n - 1) + fib(n - 2)
    fibs+= n -> result
    return result
  }
}
println(fib(100))

错误是:

递归fib需求类型

我已经尝试在各个地方为闭包输入一个返回类型,但我似乎无法让它工作.

声明闭包会val fib = (n: Int): Int => {产生不同的编译错误.

你能帮我解决这个编译错误吗？

Answer 1

您可以根据Ben Jackson(即def fib (n: Int): Int = ...)的建议定义一种方法.

函数值不能递归.编辑:事实证明他们可以递归 ; 你只需要更多地帮助类型推理器.而且,你需要摆脱return; 它只能用在方法中.

以下作品:

var fibs = Map.empty[Int, Int]
fibs += 0 -> 1
fibs += 1 -> 1
fibs += 2 -> 2
val fib: (Int => Int) = n => {
  if(fibs contains n) 
    fibs(n)
  else {
    val result = fib(n - 1) + fib(n - 2)
    fibs += n -> result
    result
  }
}
println(fib(100))

此外,你应该看一下这篇博客文章,了解如何借助lambdas抽象出memoization逻辑.