"Simple" Recursive number sequence?

Hi there everybody. I'm somewhat new to recursion. I've been given the task of try to generate the Catlan numbers recursively. I know there's a function for this but we're supposed to use recursion and have a subfunction - I'm not even quite sure what the subfunction is supposed to do. This isn't supposed to be a "really" hard problem... but I think that might be a slight exaggeration by the professor (I've seen how to do this type of stuff with for loops...etc).

This is what I have so far:

 function C = CatNum(n)
if n == 0
    C = 1;
else    
    C = 0;
    cat_sum(n);
end
    function cat_sum(m)   
        C = C+ CatNum(m-1)*CatNum(n-m);        
        if m == n  % not sure about this          
            cat_sum(****); % or this
        end

    end
end

You can see the nested subfunction cat_sum is where I think the real action happens. If anyone is feeling bored, it would be cool to know what I'm supposed to do. Thanks very much! :)

Answer 1

[Star Strider]

I had to look up Catalan number but it seems a relatively straightforward recursive calculation (if the relation you were given is the same as the Wikipedia description). Unless you’re using logarithms to compute them (in which instance the recursion is a sum), the recursion is a product. If you are supposed to use a subfunction, I would use it to calculate (n+k)/k (or its log), with the main function doing the recursive multiplication (or addition).

Sketching:

function C = CatNum(n)
    if n < 2
        C = 1;
    else
        C = exp(log_cat_sum(n));
    end
    function log_cat_sum = cat_sum(m)
        log_cat_sum = 0;
        for k = 2:m
             log_cat_sum = log_cat_sum + log((m+k)/k);
        end
    end
end

n = 6
C = CatNum(n)

[Michael]

Hi there - thanks for the response!

The specific problem has a template. I filled in what I thought was correct but after seeing yours, I think even my base case was incorrect.

Basically to do it using a for loop I would have:

function C = catalan(n)
if n == 0
  C = 1;
else
  C = 0;
  for i = 1:n
      C = C + catalan(i-1)*catalan(n-i);
  end
end

end

No problem. But this problem has the form:

 function C = CatNum(n)
if n 
    C =
else    
    C = 
    cat_sum(n);
end
    function cat_sum(m)   
        C = C+ CatNum(m-1)*CatNum(n-m);        
        if m             
            cat_sum(            );
        end

    end
end

So I'm thinking that what I had initially was wrong. Does this make any type of sense? I have the definition of the Catlan numbers below

%

[Roger Stafford]

There is another recursion formula that looks more efficient to me

 C(0) = 1
 C(n+1) = 2*(2*n+1_/(n+2)*C(n)

[Star Strider]

Michael — My pleasure! Correct, but note that the individual Cn (to be accumulated in cat_sum) are defined by using nchoosek, at least according to the Wikipedia article on Catalan number - Properties.

Roger — You’re correct (when are you not?) but this seems to be a homework or take home exam problem, and is constrained by the problem statement. It appears to require a summation, and I was taking a wild guess as to what it was. I value your comments, and always learn from them.