#### Archived

This topic is now archived and is closed to further replies.

# Recursion

This topic is 5963 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

What is recursion, and why is it good/bad ? Everyone say wow. www.crisis51.com

##### Share on other sites
That''s this one.

Everyone say wow.
www.crisis51.com

##### Share on other sites
Lol, Nice one DrPizza!

Recursion is a function calling itself. It's good because it can simplify things (e.g. binary trees) but is bad because it uses a lot more stack space (you need to push stuff onto the stack each call) and it's generally not as quick as an iterative solution. Example code:

    #include <cstdio>void doRecursion(int howManyTimes){    if (howManyTimes == 0)      return;    else    {      printf("3 times %d = %d\n", howManyTimes, 3*howManyTimes);      doRecursion(howManyTimes - 1);    }}int main(){	doRecursion(10);	return 0;}

Alimonster

"If anyone can show me, and prove to me, that I am wrong in thought or deed, I will gladly change. I seek the truth, which never yet hurt anybody. It is only persistence in self-delusion and ignorance which does harm." -- Marcus Aurelius

[edited by - Alimonster on March 24, 2002 10:23:23 AM]

##### Share on other sites
Gods DrPizza, that really cracked me up.

But since tom76 didn''t get it, allow me to explain it in more "programming-oriented" terms.

A recursive function is basically a function that calls itself in order to solve a given problem.
Consider a function to calculate factorials (the factorial of a number n is all integer up to and including n multiplied (so 5 factorial = 1 * 2 * 3 * 4 * 5)).
The iterative (non-recursive) version of such a function might look like this:

  int factorial (int n) {    int total = 1;    for (int i = 1; i <= n; i++)        total = total * i;    return total;}

A recursive version of the same function might be:

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

In this kind of simple example the advantages/disadvantages of recursion isn''t really obvious. In most cases where recursion is a simple option it will often result in somewhat more readable code (I know, I know... not everyone agrees with that).
Recursive functions are, however, more demanding on resources (especially the stack).

There is no recursive algorithm that cannot also be implemented as an iterative algorithm, but in some cases the recursive algorithm will be a lot easier to code, and much more readable.

So, in conclusion, recursive algorithms are sometimes easier to read and/or write, but are usually less efficient (in terms of resources) than iterative ones. And you can always take a recursive algorithm and rewrite it as an iterative one.

Neophyte

- Death awaits you all with nasty, big, pointy teeth. -

##### Share on other sites
Tail recursion with a suitable compiler has no stack usage penalty.

All recursions can be written as an iteration, but a number of recursions require iteration with a stack, in which case it''s generally easier to use the recursion-supplied stack than it is to implement your own.

For many problems, it''s the obvious way of coding something (example: traversal of a simple two-pointer binary tree).

##### Share on other sites
I got the joke, a little late but I got it lol. Very clever indeed.

Thanks for clearing up the recursion, that''s a big help!

1. 1
2. 2
Rutin
24
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 28
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631772
• Total Posts
3002260
×