Ошибка компиляции рекурсивного замыкания в Scala

Question

Я пытаюсь реализовать запомненную функцию числа Фибоначчи, и у меня возникает ошибка компиляции, которую я не могу разобрать.Следующий код - это то, что у меня есть.

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

Вы можете определить метод, предложенный Беном Джексоном (т.е. 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))

---

Также вам следует взглянуть на этот пост , чтобы понять, как можно абстрагировать логику запоминания с помощью лямбд.

Answer 2

Вы должны явно установить тип возвращаемого значения рекурсивных функций. Он не может вывести тип, потому что вывод будет циклическим. Итак: def fib (n: Int): Int = ...

Answer 3

Избавьтесь от return, поскольку они могут использоваться только с def, а не val, и объявите тип fib, поскольку это требование Scala для рекурсивных определений.

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

Обратите внимание, что fib(100) переполнит Int