Erreur de compilation Scala récursive fermeture

Question

J'essaye d'implémenter une fonction numérotée de nombre de Fibonacci, et je cours dans une erreur de compilation que je ne peux pas trier. Le code suivant est ce que j'ai jusqu'ici.

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

L'erreur est:

récursives fib besoins de type

J'ai essayé d'entrer un type de retour pour la fermeture en divers endroits, mais je ne peux pas sembler l'obtenir travailler.

Déclarer la fermeture comme val fib = (n: Int): Int => { donne une erreur de compilation différente.

Pourriez-vous s'il vous plaît m'aider à corriger cette erreur de compilation?

Answer 1

Vous devez définir explicitement le type de retour des fonctions récursives. Il ne peut pas déduire le type parce que l'inférence serait cyclique. Donc: def fib (n: Int): Int = ...

Answer 2

Vous pouvez définir une méthode comme suggéré par Ben Jackson (c'est-à-dire def fib (n: Int): Int = ...).

Les valeurs de fonction ne peuvent pas être récursives. EDIT: Il s'avère they can be recursive; vous avez juste besoin d'aider l'inferenceur de type un peu plus. En outre, vous devez vous débarrasser de return; il ne peut être utilisé dans les méthodes.

Les travaux suivants:

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

---

Aussi, vous devriez jeter un oeil à this blogpost pour comprendre comment vous pouvez abstraire la logique memoization avec l'aide de lambdas.

Answer 3

Débarrassez-vous de la return, car ils ne peuvent être utilisés avec def, non val et déclarer le type de fib, comme c'est une exigence Scala pour les définitions récursives.

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

Notez que fib(100) débordera un Int