CODEWITHSUNDEEP
javascalarecursionnumbersrecursive-datastructures
appcodix
appcodix

Reputation: 342

Catalan Number recursive in Scala

I know how to calculate the Catalan Number in java, which is pretty straight forward:

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

But I can't imagine how to do this in Scala, because I'm totally new to it. Is it possible to do this without the use of var ?

I tried the following, but it doesn't work:

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

}

Thanks in advance :)

Upvotes: 0

Views: 461

Answers (2)

tkachuko
tkachuko

Reputation: 1986

I am using fold instead of res += piece and the rest of logic is the same as in your java algorithm:

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

Upvotes: 2

thoredge
thoredge

Reputation: 12601

How about this?

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

Here I do the same as your java-implementation, but instead of a var I use a range (0 until n) and uses that to create a sum.

The implementation performance could benefit heavily from memoization.

Upvotes: 2

Related Questions