Click here to Skip to main content
15,355,301 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Which factor are important to design a recursive program?or how we think recursively?:confused:
Posted
Updated 24-Sep-10 9:27am
v3

The main reasons to use recursion are:

- Your a Computer Science student. If you want a good grade you will see everything as recursive even when it's not necessarily the best way of doing things

- In C++ you're doing something at runtime that can be represented far more simply using recursion

- In C++ you're using some form of compile time metaprogramming with types. The only way you can iterate over types at compile time is recursively
   
Comments
Emilio Garavaglia 24-Sep-10 16:22pm
   
I vote for the first point!
Paul Michalik 26-Sep-10 5:19am
   
I vote for the 3rd point.
"how we think recursively": See here[^]
   
Comments
Marc A. Brown 24-Sep-10 12:22pm
   
heh
Henry Minute 24-Sep-10 14:57pm
   
I didn't even check your link. I'm guessing where it leads. :)
Emilio Garavaglia 24-Sep-10 16:21pm
   
That's not a recursion...
Just a vulgar loop! (done with a GOTO!)
Aescleal 27-Sep-10 6:55am
   
It is recursion Emilio, the back button is the return statement.
There are some good articles and papers that have been published on the net. For e.g. have a look at this[^] article.
   
Q1.: re-entrancy
Q2.:
- try to convince your brain to forget it's pattern-based way of working
- Take a prolog or lisp lesson if you can - I however cannot recommend it, the above step did not work for me.
   
Comments
Aescleal 25-Sep-10 11:33am
   
Try Haskell - it's the first functional language I've learned that I ended up thinking: "Good <insert deity="" here="">, this is actually useful and understandable!!"
Paul Michalik 26-Sep-10 5:08am
   
Hm, I am not sure if I would set "recursive" = "functional"... Anyway, I'd in turn recommend F# and a very interesting concept called "Axum", a language targeting asynchronous applications with functional and imperative features. If I had to summarize that from my point of view: purely functional languages are confusing me. On the other hand, I seem to have much less problems with the functional features of imperative object-oriented languages - which indeed are useful and understandable...
a recursive programming example:

let's compute N! = N*(N-1)*(N-2)*....*2*1
int ComputeN(int N)
{
   assert(N >= 1);
   if(N > 1)
     return N*ComputeN(N-1);
   else
     return 1;
}
   
v2
A recursive solution will make use of itself until a base case is reached. So, you keep asking it to ask itself to do stuff until it reaches a known case, at which point it is done. For example, to multiply two positive integers, consider this recursive example:

C#
// Returns a * b.
int Multiply(int a, int b)
{
    
    // Base case.
    if(a == 1) return b;
    
    // Other cases. a * b = (a - 1) * b + b.
    return Multiply(a - 1, b) + b;
    
}


You could add error checking for negative and zero numbers or what have you, but that's not the point. First, you provide a base case (any number times 1 will be that number). Then, you call Multiply with a different value, assuming it will return the proper value to you. Once you have that value, you can perform a simple addition to return the value to the current call. This function will call itself over and over, simplifying the problem each time, until the base case is reached and the results are propogated up the call stack to produce the final answer.

Here is the iterative version, for comparision:

C#
// Returns a * b.
int Multiply(int a, int b)
{
    
    // Keep adding b. a * b = b + b + b + b + ... + b.
    int sum = 0;
    while(a > 0)
    {
        sum += b;
        a--;
    }
    
    // Done.
    return sum;
    
}


Note that it doesn't call itself. And it doesn't really have a base case (just a terminating condition).
   
To further confuse the matter, here's the compile time version of the above... :)
namespace Tests {

    template <int NumberA, int NumberB>
    struct Product {
        enum {
            Value = Product<NumberA - 1, NumberB>::Value + NumberB
        };
    };

    template <int Number>
    struct Product<1, Number> {
        enum {
            Value = Number
        };
    };

    template <int Number>
    struct Product<0, Number> {
        enum {
            Value = 0
        };
    };

}

Now following code generates the output shown below...:
std::cout << "1*5 = " << Tests::Product<1, 5>::Value << std::endl;
std::cout << "5*1 = " << Tests::Product<1, 5>::Value << std::endl;
std::cout << "0*0 = " << Tests::Product<0, 0>::Value << std::endl;
std::cout << "2*5 = " << Tests::Product<2, 5>::Value << std::endl;
std::cout << "3*4 = " << Tests::Product<3, 4>::Value << std::endl;
std::cout << "12*3 = " << Tests::Product<12, 3>::Value << std::endl;
std::cout << "5*0 = " << Tests::Product<5, 0>::Value << std::endl;
std::cout << "0*5 = " << Tests::Product<0, 5>::Value << std::endl;


1*5 = 5
5*1 = 5
0*0 = 0
2*5 = 10
3*4 = 12
12*3 = 36
5*0 = 0
0*5 = 0
Hit enter to continue..
   
v3
In most examples, recursion can be replaced with template metaprogramming or a loop. Unless you know that the recursion depth will be small, recursion is best suited for benchmarking the results of your solution using a loop or metaprogramming.
   
v2
// Which factor are important to design a recursive program ?
At the design time,
it is very important to find a replacement for a recursive code... :)

// or how we think recursively ?
I would use the recursion calls
at the same-kind-stack routines triggered by the not permanent events,
which can be nested and their count can not be precalculated (looped) :) :
void ProcessTreeFromRoot(CYourTeeObject* pcTreeObject,
                         HTREEITEM hRoot /*root of any tree structure*/,
                         LPARAM lPar)
{
  HTREEITEM hChild = pcTreeObject->GetFirstChild(hRoot);
  while (hChild) {
    ProcessTreeFromRoot(pcTreeObject, hChild, lPar); // the same, with the sub-root
    hChild = pcTreeObject->GetNextChild(hRoot);
  }
  // There are no children more/yet, process the root itself:
  SomethingForATreeRoot(pcTreeObject, hRoot, lPar);
}
   
You can think recursive only if you're God, because, you know:

"To iterate is human, to recurse divine."


--(L. Peter Deutsch)


:)
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900