retagged by
1,636 views
3 votes
3 votes

I'm solving questions of recursion. But those problems are hard to debug in few minutes? Have you any such method that solve recursive problem in less time? I have written problem below: please help me in this problem:

int fun(int n){
    int x=1,k;
    if(n==1) return x;
    for(k=1; k<n;
    x=x+fun(k)*fun(n-k);
    return;
}

The return value of fun(5) is ________.

How to solve this problem in less time? Please help me.

retagged by

1 Answer

Best answer
4 votes
4 votes
Calculate the value of the function for smaller values first, then calculate for the next larger value, and so on.

For example, in this question, calculate in the sequence $f(1) \to f(2) \to f(3) \to f(4) \to f(5)$

If you try to calculate from top to bottom, you will end up evaluating the function for an exponential number of times.

So,

$f(1)=1$
$f(2)=2$
$f(3)=5$
$f(4)=15$
$f(5)=51$

Related questions

0 votes
0 votes
1 answer
1
kallu singh asked Dec 14, 2017
374 views
0 votes
0 votes
2 answers
2
Akash Mishra asked Jul 7, 2017
542 views
What is the value of F(n, m)?Function F(n, m : integer) : integer; begin if(n <= 0) or (m <= 0) then F:=1 else F := F(n-1, m) + F(n, m-1); end;
2 votes
2 votes
4 answers
3
gate_forum asked Mar 16, 2017
1,445 views
output of program:void function(int); void main() { function(3); } void function(int num){ if(num>0) { function( num); printf("%d",num); function( num); } }will the argum...
5 votes
5 votes
2 answers
4
shekhar chauhan asked Jun 28, 2016
1,460 views
Can Someone explain either Tree or Stack method to trace out this recursion ?What is the output of this Program ?