int Fun(int m, int n)
{
if(n==0)
{
return n 2;
}
return Fun(n-1, m-1) Fun(m-1,n-1) 1;
}
I'm completely lost as to what the 1st case would visually look like for this function. I don't understand why the function has two parameters and why we only return 1 parameter at the end with our base case. What would be the process to work this out? Any input you want to use to explain to me is fine I was trying (3,3). Although, now that I'm thinking about it how would this function look like if one of the inputs was smaller than the other like (3,2) or (2,3)?
CodePudding user response:
Note that return n 2;
simplifies to return 2;
.
The function takes two arguments (parameters) and returns a single value. That's like the operation of adding two numbers that you were taught in your first year at school.
Whether or not Fun(n - 1, m - 1)
is called before Fun(m - 1, n - 1)
is not specified by the C standard. So I can't tell you what the first recursive call will look like. This gives compilers more freedom in making optimisation choices. Of course the order in which the functions are called has no effect on the eventual result.
The best way of analysing what happens in your particular case is to use a line by line debugger.
CodePudding user response:
There is nothing special about recursive functions - they work exactly like non-recursive functions.
Fun(3,3)
does this:
if(3==0)
{
return 3 2;
}
return Fun(2, 2) Fun(2, 2) 1;
It needs the value of Fun(2,2)
, which does this:
if(2==0)
{
return 2 2;
}
return Fun(1, 1) Fun(1, 1) 1;
And that needs Fun(1,1)
, which does
if(1==0)
{
return 1 2;
}
return Fun(0, 0) Fun(0, 0) 1;
and Fun(0,0)
does
if(0==0)
{
return 0 2;
}
return Fun(-1, -1) Fun(-1, -1) 1;
which returns 2 since the condition is true.
So, Fun(1, 1)
will do
return 2 2 1;
which is 5, and Fun(2,2)
will do
return 5 5 1;
which is 11, and Fun(3,3)
will do
return 11 11 1;
which is 23.
I'm sure you can work through other examples on your own.