Solved

a  problem of function recursion

Posted on 2002-07-11
6
221 Views
Last Modified: 2010-04-15
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 :)
0
Comment
Question by:China_Ark
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
6 Comments
 
LVL 12

Accepted Solution

by:
pjknibbs earned 50 total points
ID: 7148464
I'm not sure what your difficulty is. Basically, the code in the "ELSE" section simply calls the recursive function again with different values--the IF statement is there to make sure the recursion ends at some point, because if the function ALWAYS called itself you'd get into an infinite loop and would crash with a stack space error.

Basically, the above code calls RecuFun(5). RecuFun(5) returns the value of RecuFun(4) + RecuFun(3). RecuFun(3) returns the value of RecuFun(2) + RecuFun(1). RecuFun(1) returns 1, ending the recursion down that branch. (Note I've missed one of the recursive calls at each level here).

It's perhaps easier to understand if you only have one recursive call in the function, e.g.

int factorial(int n)
{
  if (n == 1)
    return 1;
  else
    return n * factorial(n - 1);
}

This function calculates a factorial (e.g. factorial(6) = 6*5*4*3*2*1).
0
 
LVL 3

Expert Comment

by:cincin77
ID: 7148976
an implementation of fibonacci numbers
what exactly did not you understand?
do you know about fibonacci numbers?
0
 

Author Comment

by:China_Ark
ID: 7150132
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.
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:China_Ark
ID: 7150138
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.
0
 
LVL 2

Expert Comment

by:jonnin
ID: 7161869
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 ...

0
 
LVL 45

Expert Comment

by:Kent Olsen
ID: 9480511
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
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

734 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question