CODEWITHSUNDEEP
javaalgorithmrecursion
Hunter
Hunter

Reputation: 25

Programming a recursive method for summation from i to n

I am trying program a recursive method for summation from i to n for the following equation where f(0)=f(1)=1.

f(n) = from i = 1 to n ∑f(i-1) * f(n-i)

This is what I have so far, which is giving me a stack overflow error when n=4

Upvotes: 0

Views: 894

Answers (3)

Dawnkeeper
Dawnkeeper

Reputation: 2877

For a recursive sum you will get something like this:

public int sum(int start, int end)
{
  if(start >= end)
  {
    return end;
  }
  return start +sum(start+1,end);
}

This scheme can be adapted to the formulas you want to use:

 static long c(long x)
  {
    if(x <2) return 1;
    return sumC(1,1,x);
  }

  static long sumC(long start,long current,long stop)
  {
      if(current>stop) return 0;
      return c(current-1)*c(stop -current) + sumC(start,current+1,stop);
  }

0 to 10 : 1 1 2 5 14 42 132 429 1430 4862 16796

Upvotes: 0

Anderson Vieira
Anderson Vieira

Reputation: 9049

If you really need to use recursion, your function would look like this:

static long catalan(int n) {
    return c(1, n);
}

static long c(int i, int n) {
    if (n <= 1) {
        return 1;
    } else if (i > n) {
        return 0;
    } else {
        return catalan(i - 1) * catalan(n - i) + c(i + 1, n);
    }
}

Although, as others have said, a version that uses memoization will be much faster, this will be fine if you're doing it only for learning and testing.

  • if (n <= 1) return 1 is your base case.
  • else if (i > n) return 0 is to stop the sum when i gets greater than n.
  • return catalan(i - 1) * catalan(n - i) + c(i + 1, n) is the summation, where i is increased by 1 until it reaches n.

Upvotes: 1

Matthew Franglen
Matthew Franglen

Reputation: 4532

Your method does not match the equation you have provided. You state that:

n ∑c(i-1)*c(n-i)

but your final return statement is:

c(i-n) * c(i-1)

Perhaps you should try:

c(n-i) * c(i-1)

When I pass in 4 it generates the following call stack:

i = 0, n = 4
  c(i - n) with i = 1

i = 1, n = -3
  c(i - n) with i = 1

i = 1, n = 4
  c(i - n) with i = 2

i = 2, n = -2
  c(i - n) with i = 2

i = 2, n = 4
  c(i - n) with i = 3

i = 3, n = -1
  c(i - n) with i = 3

i = 3, n = 4
  c(i - n) with i = 4 becomes c(0) becomes 1
  c(i - 1) with i = 4

i = 4, n = 3
  c(i - n) with i = 4 becomes c(1) becomes 1
  c(i - 1) with i = 4 becomes c(3) and it repeats from this point on

So basically when i reaches 4 and you have an n of 3 you end up calling c(3) which then triggers calling c(i - 1) a.k.a. c(3) again and again.

If you make the change I suggested then the same invocation calls:

c(n - i) -> c(4 - 1)
  c(n - i) -> c(3 - 2) -> c(1) -> 1
  c(i - 1) -> c(1) -> 1
c(i - 1) -> c(1) -> 1

On the last line i has become 2 even though that is at the top level, due to the shared nature of that variable.

Upvotes: 1

Related Questions