When and Why Recursion
Author
Hello folks,
I really would like to know when and why you would use recursion? In what cases does it make sense to use recursion?
Is there speed improvements using a recursion algorithm? At what threshold do you begin to loose the effectiveness of using a recursion algorithm? Could this be measured in the number of lines that defines your algorithm?
My biggest fear of using recursion is that it could be incredibly hard to debug if there is a problem.
I do understand that sometimes, recursion can be of great benefit, but I have seen code that use it almost everywhere they can.
Any pointers on using recursion or other techniques that can/do replace using recursion?
Recusion gets you points for style basically. It''s always faster
to find an iterative solution. Howver if your data is inherently
recursive, your not going to do much better. Printing a binary
tree in sorted order is much easyer with recursion.
to find an iterative solution. Howver if your data is inherently
recursive, your not going to do much better. Printing a binary
tree in sorted order is much easyer with recursion.
void CNode::in_order(ostream &os=cout) {
if(m_pLeft) m_pLeft->in_order(os);
os << m_pData;
if(m_pRight) {
os << ", ";
m_pRight->in_order(os);
}
}
<\code>
On the other hand tail recursion doesn''t get you anything but an
empty cache.
Data* CNode::find(const KeyType &k) {
if(k == Key) return m_pData;
else if(k < Key) {
return (m_pLeft)?m_pLeft->find(k):0;
} else {
return (m_pRight)?m_pRight->find(k):0;
}
}
// It''s much better to do;
Data* CNode::find(const KeyType &k) {
CNode *p=this;
while(p) {
if(k == p->Key) return p->m_pData;
else p = (kKey)?p->m_pLeft:p->m_pRight;
}
return 0;
}
<\code>
The first version is all kinds of ugly, it will fill the stack
with useless data, and I have to guard aginst dereferenceing a NULL pointer.
It''s something that comes with experiance, but finding a good
recusive solution to something is one of the more fun things
you can do at a computer while typeing with both hands.
-- Grib
Recursion is usually the best implementation for problems that have a "divide-and-conquer" solution. Examples are integer power (I think it''s called the peasant''s algorithm in some circles?) and quicksort. Though the previous poster''s correct--every recursive solution can be made iterative--sometimes the iterative solution is more straightforward.
Im not positive if it''s true or not but someone once told me a portal engine uses recursion.
Recursion can be used for some functions:
The transformation of a number from a base (octal, hexadecimal, decimal, etc.) into another...
"Everything is relative." -- Even in the world of computers.
{ n+1 if m=0Ackermannn: Ack(m,n)= { Ack(m-1,1) if n=0 { Ack(m-1,Ack(m,n-1)) otherwise[/source]The calculus of (n!)The Fibonacci seriesThe largest common divider of 2 numbersThe Manna-Pnueli function[source] { x-1 if x>=12F(x)= { F(F(x+2)) otherwise The transformation of a number from a base (octal, hexadecimal, decimal, etc.) into another...
"Everything is relative." -- Even in the world of computers.
quote:Original post by Stoffel
Though the previous poster''s correct--every recursive solution can be made iterative--sometimes the iterative solution is more straightforward.
Please, give an example. I''ve never seen an iterative solution of a recursive problem (i.e. the divide and conquer sort) be ''more straightforward''. I have seen recursive solutions to problems that are iteratively obvious and can be done obscurely by recursion (though I can think of any right now). Just wondering.
Also, does your definition of ''more straightforward'' take into account the developers understanding of the stack? After all, an iterative solution to a recursive problem essentially comes down to writing your own specialized stack.
Mike Roberts
aka milo
mlbobs@telocity.com
Here''s an example:
(it calculates the sum of the digits of one number)
"Everything is relative." -- Even in the world of computers.
(it calculates the sum of the digits of one number)
//Iterativeint n,s=0;void main(void){ printf("n=");scanf("%d",&n); while(n!=0) { s+=n%10; n/=10; } printf("s=%d",s);}// Recursiveint n;int s(int n){ if(n==0) { return 0; } else { return n%10+s(n/10); }}void main(void){ printf("n=");scanf("%d",&n); printf("s=%d",s(n));} "Everything is relative." -- Even in the world of computers.
Milo:
uhhh, I mis-typed.
I MEANT to say, "Though the previous poster''s correct--every recursive solution can be made iterative--sometimes the recursive solution is more straightforward."
heh, sorry.
uhhh, I mis-typed.
I MEANT to say, "Though the previous poster''s correct--every recursive solution can be made iterative--sometimes the recursive solution is more straightforward."
heh, sorry.
Recursion solves:
maze navigation
branching problems
octrees
fractal generation
AI problem solving
bintrees
ray tracing
portal engines
generation of plant forms
calculation of problems which rely on solutions from sub-problems
root finding
language interpretation
language compilation
natural language parsing
hierarchical radiosity
If you think there is always an iterative solution that is not too complex that can solve the same problem then you havn''t explored too many recursive problems.
Yeah, sure, some of the above can be done with iterative solutions. Go ahead and try it.
maze navigation
branching problems
octrees
fractal generation
AI problem solving
bintrees
ray tracing
portal engines
generation of plant forms
calculation of problems which rely on solutions from sub-problems
root finding
language interpretation
language compilation
natural language parsing
hierarchical radiosity
If you think there is always an iterative solution that is not too complex that can solve the same problem then you havn''t explored too many recursive problems.
Yeah, sure, some of the above can be done with iterative solutions. Go ahead and try it.
I posted a solution to a maze navigation problem, using recursion on another forum at the AI section (http://www.gamedev.net/community/forums/topic.asp?topic_id=17619&forum_id=9&Topic_Title=I+WOULD+LIKE+SOME+PARTNERS%2C+OR+SOME+HELP+ON+MY+PRO&forum_title=Artificial+Intelligence&M=True&S=True). There, 2 computer characters must find each other in the maze.
"Everything is relative." -- Even in the world of computers.
"Everything is relative." -- Even in the world of computers.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
