15,355,301 members
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

## Solution 2

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
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.

## Solution 1

"how we think recursively": See here[^]
Marc A. Brown 24-Sep-10 12:22pm

heh
Henry Minute 24-Sep-10 14:57pm

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.

## Solution 3

There are some good articles and papers that have been published on the net. For e.g. have a look at this[^] article.

## Solution 4

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.
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...

## Solution 5

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

## Solution 6

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).

## Solution 7

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

## Solution 8

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

## Solution 9

// 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);
}```

## Solution 10

You can think recursive only if you're God, because, you know:

"To iterate is human, to recurse divine."

--(L. Peter Deutsch)

:)