Click here to Skip to main content
16,014,667 members
Home / Discussions / C / C++ / MFC
   

C / C++ / MFC

 
GeneralHelp with random numbers... Pin
Snyp22-Oct-03 15:19
Snyp22-Oct-03 15:19 
GeneralRe: Help with random numbers... Pin
d00_ape23-Oct-03 1:50
sussd00_ape23-Oct-03 1:50 
GeneralRe: Help with random numbers... Pin
David Crow23-Oct-03 4:10
David Crow23-Oct-03 4:10 
QuestionI still have no idea how do we benefit from rescursion? Pin
Link260022-Oct-03 12:55
Link260022-Oct-03 12:55 
AnswerRe: I still have no idea how do we benefit from rescursion? Pin
Michael Dunn22-Oct-03 14:17
sitebuilderMichael Dunn22-Oct-03 14:17 
GeneralRe: I still have no idea how do we benefit from rescursion? Pin
Link260022-Oct-03 14:31
Link260022-Oct-03 14:31 
GeneralRe: I still have no idea how do we benefit from rescursion? Pin
Ravi Bhavnani22-Oct-03 21:52
professionalRavi Bhavnani22-Oct-03 21:52 
GeneralRe: I still have no idea how do we benefit from rescursion? Pin
David Crow23-Oct-03 6:17
David Crow23-Oct-03 6:17 
Just because a loop has been eliminated does not make the algorithm more beneficial. All recursive algorithms can be converted to iterative algorithms. There are pros and cons to doing so. Some benefit the programmer, others benefit the computer.

Recursion seems a natural fit when a larger problem can be broken down into one or more smaller problems, using solutions to the smaller problems to solve the original problem. If a few basic rules are followed, recursion is easy (relatively speaking) and practical: 1) Base cases that can be solved without recursion; 2) Making progress towards a base case; 3) Design rule that assumes all recursive calls work; 4) Compound interest rule never duplicates work by solving the same instance of a problem in a separate recursive call.

Consider the recursive implementation of Fibonacci numbers:

long Fib( int N )
{
    if (N <= 1)
        return 1;
    else
        return Fib(N - 1) + Fib(N - 2);
}


It seems innocent enough, but for values of N > 30, it's inefficient. Its running time grows exponentially because of all the redundant work (compound interest rule). To compute Fib(N), there is one call to Fib(N - 1) and Fib(N - 2). However, since Fib(N - 1) recursively calls Fib(N - 2) and Fib(N - 3), there are actually two separate calls to Fib(N - 2). Similarly, Fib(N - 3) is computed three times, Fib(N - 4) is computed five times, Fib(N - 5) is computed eight times, etc. These results are thrown away and recomputed later on.


Five birds are sitting on a fence.
Three of them decide to fly off.
How many are left?

AnswerRe: I still have no idea how do we benefit from rescursion? Pin
Shog922-Oct-03 21:50
sitebuilderShog922-Oct-03 21:50 
GeneralTemplate question. Pin
WREY22-Oct-03 12:24
WREY22-Oct-03 12:24 
GeneralRe: Template question. Pin
Michael Dunn22-Oct-03 12:38
sitebuilderMichael Dunn22-Oct-03 12:38 
GeneralNeed to refresh property page controls Pin
ElizabethC22-Oct-03 12:04
ElizabethC22-Oct-03 12:04 
GeneralRe: Need to refresh property page controls Pin
David Crow27-Oct-03 8:11
David Crow27-Oct-03 8:11 
GeneralRe: Need to refresh property page controls Pin
ElizabethC27-Oct-03 8:28
ElizabethC27-Oct-03 8:28 
GeneralHTML Help in Chinese Pin
Wolfram Steinke22-Oct-03 11:48
Wolfram Steinke22-Oct-03 11:48 
Generalproblem with thread Pin
Deepak Samuel22-Oct-03 11:35
Deepak Samuel22-Oct-03 11:35 
GeneralRe: problem with thread Pin
Ryan_Roberts22-Oct-03 12:02
Ryan_Roberts22-Oct-03 12:02 
GeneralSystem.SByte* is inaccessible... Pin
almogaver22-Oct-03 11:06
almogaver22-Oct-03 11:06 
QuestionArray of pointers on the heap? Pin
Rickard Andersson2022-Oct-03 9:07
Rickard Andersson2022-Oct-03 9:07 
AnswerRe: Array of pointers on the heap? Pin
David Crow22-Oct-03 9:22
David Crow22-Oct-03 9:22 
GeneralRe: Array of pointers on the heap? Pin
Rickard Andersson2022-Oct-03 9:26
Rickard Andersson2022-Oct-03 9:26 
GeneralRe: Array of pointers on the heap? Pin
Rickard Andersson2022-Oct-03 9:35
Rickard Andersson2022-Oct-03 9:35 
GeneralRe: Array of pointers on the heap? Pin
David Crow22-Oct-03 9:59
David Crow22-Oct-03 9:59 
GeneralRe: Array of pointers on the heap? Pin
Jeryth30-Oct-03 10:54
Jeryth30-Oct-03 10:54 
AnswerRe: Array of pointers on the heap? Pin
Nitron23-Oct-03 8:07
Nitron23-Oct-03 8:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.