Recursion
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:
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]
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]
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:
A recursive version of the same function might be:
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. -
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. -
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).
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).
Author
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!
Thanks for clearing up the recursion, that''s a big help!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
