Scala recursive closure compile error

Question

I am trying to implement a memoized Fibonacci number function, and I am running into a compile error that I can't sort out. The following code is what I have so far.

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

The error is:

Recursive fib needs type

I have tried entering a return type for the closure in various places, but I can't seem to get it to work.

Declaring the closure like val fib = (n: Int): Int => { yields a different compile error.

Could you please help me fix this compile error?

Answer 1

You can define a method as suggested by Ben Jackson (i.e. def fib (n: Int): Int = ...).

Function values cannot be recursive. EDIT: It turns out they can be recursive; you just need to help the type inferencer a bit more. Also, you need to get rid of return; it can only be used in the methods.

The following works:

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

---

Also you should take a look at this blogpost to understand how you can abstract away the memoization logic with help of lambdas.

Answer 2

You have to explicitly set the return type of recursive functions. It can't infer the type because the inference would be cyclic. So: def fib (n: Int): Int = ...

Answer 3

Get rid of the return, as they can only be used with def, not val, and declare fib's type, as that's a Scala requirement for recursive definitions.

val fib: (Int => Int) = (n: Int) => {
  if (fibs.contains(n)) fibs.apply(n)
  else{
    val result = fib(n - 1) + fib(n - 2)
    fibs+= n -> result
    result
  }
}

Note that fib(100) will overflow an Int