Katalanisch Anzahl rekursiven in Scala

Question

Ich weiß, wie die katalanische Zahl in Java zu berechnen, was ziemlich geradlinig ist:

int catalan(int n) { 
    int res = 0; 

    // Base case 
    if (n <= 1) { 
     return 1; 
    } 
    for (int i = 0; i < n; i++) { 
     res += catalan(i) * catalan(n - i - 1); 
    } 
    return res; 
} 

Aber ich kann nicht vorstellen, wie dies in Scala zu tun, weil ich total bin neu dazu. Ist es möglich, dies ohne die Verwendung von Var zu tun?

habe ich versucht, die folgenden, aber es funktioniert nicht:

object Catalan { 

    def catalan: Int => Int = n => { 
    val res = 0 
    val i = 0 

    if (n <= 1) 1 
    else for (i <- 0 to n-1) res += catalan(i) * catalan(n - i - 1) 
    } 

} 

Vielen Dank im Voraus :)

Answer 1

Wie wäre das?

def catalan(n: Int): Int = 
    if (n <= 1) 1 
    else (0 until n).map(i => catalan(i) * catalan(n - i - 1)).sum 

Hier kann ich die gleiche wie Ihr Java-Implementierung, aber anstelle eines var verwende ich einen Bereich (0 bis n) und verwendet diese eine Summe zu erstellen.

Die Implementierungsleistung könnte stark von Memoization profitieren.

Answer 2

I fold statt res += Stück und der Rest der Logik verwende ist das gleiche wie in der Java-Algorithmus: https:

def catalan(n: Int): Int = { 
     if (n <= 1) 1 
     else (0 until n).fold(0)((acc, i) => acc + catalan(i) * catalan(n - i - 1)) 
}