Jump to content
  • Advertisement

Archived

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

AlekM

When and Why Recursion

This topic is 6525 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

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?

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
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.

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Im not positive if it''s true or not but someone once told me a portal engine uses recursion.

Share this post


Link to post
Share on other sites
Recursion can be used for some functions:
    
{ n+1 if m=0
Ackermannn: 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 series
The largest common divider of 2 numbers
The Manna-Pnueli function
[source]
{ x-1 if x>=12
F(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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Here''s an example:
(it calculates the sum of the digits of one number)
    
//Iterative


int n,s=0;

void main(void)
{
printf("n=");scanf("%d",&n);
while(n!=0)
{
s+=n%10;
n/=10;
}
printf("s=%d",s);
}

// Recursive


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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!