Archived

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

Recursion

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites