asked on

a problem of function recursion

I'm primer, I didn't know well about executive process of function recursion .for example

/* a recursive function instance */
int RecuFun(int n)
{
int f1,f2;

if ( n ==1 || n == 0 )
return 1;
else {
f1 = RecuFun(n - 1);
f2 = RecuFun(n - 2);

return f1 + f2;

}
}

main()
{
int num = 5;
int result;

result = RecuFun( num );
printf("%d\n",result);
}

running result :
8

but i am confused in else sentence section. please give a explanation thanks :)

ASKER CERTIFIED SOLUTION

pjknibbs

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

cincin77

an implementation of fibonacci numbers
what exactly did not you understand?
do you know about fibonacci numbers?

China_Ark

ASKER

thanks to pjknibbs and cincin77.

Actually,it 's fibonacci function,the blow is its revise.
but still not efficent.
long RecuFun(int n)
{
long f1,f2;
if ( n ==1 || n == 0 )
return 1;
else {
f1 = RecuFun(n - 1);
f2 = RecuFun(n - 2);

return f1 + f2;
}
}

main()
{
int num;
long result;

for( num = 0;num <=40;num++) {
result = RecuFun( num );
printf("%10ld",result);
if ( (num + 1) % 4 == 0 )
printf("\n");
}
}
I don't see that as pjknibbs say, the main functin calls
RecuFun(5).
RecuFun(5) = RecuFun(4) + RecuFun(3)
_______________| |
| ________________________|
| |
| |__> RecuFun(3) = RecuFun(2) + RecuFun(1);
| ______________|
| |__> RecuFun(2) = RecuFun(1) + RecuFun(0).
|____> RecuFun(4) = RecuFun(3) + RecuFun(2);
_________________| |
| __________________________|
| |__> RecuFun(2) = RecuFun(1) + RecuFun(0);
|_____> RecuFun(3) = RecuFun(2)+ RecuFun(1);
____________|
|__>RecuFun(2) = RecuFun(1) + RecuFun(0);

RecuFun(1) returns 1, ending the recursion
down that branch.

all right? :) ok. thanks to pjknibbs and cincin77 for giving me some good word.

China_Ark

ASKER

thanks to pjknibbs and cincin77.

Actually,it 's fibonacci function,the blow is its revise.
but still not efficent.
long RecuFun(int n)
{
long f1,f2;
if ( n ==1 || n == 0 )
return 1;
else {
f1 = RecuFun(n - 1);
f2 = RecuFun(n - 2);

return f1 + f2;
}
}

main()
{
int num;
long result;

for( num = 0;num <=40;num++) {
result = RecuFun( num );
printf("%10ld",result);
if ( (num + 1) % 4 == 0 )
printf("\n");
}
}
I don't see that as pjknibbs say, the main functin calls
RecuFun(5).
RecuFun(5) = RecuFun(4) + RecuFun(3)
_______________| |
| ________________________|
| |
| |__> RecuFun(3) = RecuFun(2) + RecuFun(1);
| ______________|
| |__> RecuFun(2) = RecuFun(1) + RecuFun(0).
|____> RecuFun(4) = RecuFun(3) + RecuFun(2);
_________________| |
| __________________________|
| |__> RecuFun(2) = RecuFun(1) + RecuFun(0);
|_____> RecuFun(3) = RecuFun(2)+ RecuFun(1);
____________|
|__>RecuFun(2) = RecuFun(1) + RecuFun(0);

RecuFun(1) & ReuFun(0) returns 1, ending the recursion
down that branch.

all right? :) ok. thanks to pjknibbs and cincin77 for giving me some good word.

jonnin

recursion is not generally efficient. The extra function calls cost more if nothing else does, and there is danger of blowing the stack on larger problems. Write it iteratively, if that is too slow create a lookup table of the numbers (1 operation to get a value, no loops or computations). Of course you will have to make the table large enough for whatever problem you are solving, with notes on when the table runs out...

(you can use the output of the slow function to create the values for the table, since you have it)

to speed it up as it is, store in a static array variable the computations you have already done (cache) and get them instead of recomputing ...

Kent Olsen

No comment has been added lately, so it's time to clean up this TA.

I will leave a recommendation in the Cleanup topic area that this question is:
Accept pjknibbs' comment as answer

Please leave any comments here within the next seven days.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

Kent (Kdo)
EE Cleanup Volunteer