Archived

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

AlekM

When and Why Recursion

Recommended Posts

AlekM    100
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
Guest Anonymous Poster   
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
Stoffel    250
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
Ionut Costica    122
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
milo    122
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
Ionut Costica    122
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
Stoffel    250
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
bishop_pass    109
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
Ionut Costica    122
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
Krinkle    122
so far, everything everyone said is right, but i just want to add to this a little. Recursive is always slower than it''s iterive equivilant. This is becuase every time that a function is called, the cpu''s flags, registers and evertying are all pushed onto the stack. This takes up more time and memory... Wow, i was just thinking.. you probably don''t know about that stack either, huh? oh well... basically, recursion is much more elegant and simple. converting it to an iterive algorithm is more trouble than it is worth 90% of the time... that''s about it!

Share this post


Link to post
Share on other sites
Krinkle    122
so far, everything everyone said is right, but i just want to add to this a little. Recursive is always slower than it''s iterive equivilant. This is becuase every time that a function is called, the cpu''s flags, registers and all your local variables are pushed onto the stack. This takes up more time and memory... Wow, i was just thinking.. you probably don''t know about the stack either, huh? oh well... basically, recursion is much more elegant and simple. converting it to an iterive algorithm is more trouble than it is worth 95% of the time... that''s about it!

Share this post


Link to post
Share on other sites
Kylotan    10007
Sorry for delayed post, been away...

quote:
Original post by Krinkle

Recursive is always slower than it''s iterive equivilant. This is becuase every time that a function is called, the cpu''s flags, registers and all your local variables are pushed onto the stack.


Quick point... this isn''t entirely true... the contents of the registers and flags are not pushed onto the stack. Only the local variables are, at the start of each function.

And as for this statement from Milo: "After all, an iterative solution to a recursive problem essentially comes down to writing your own specialized stack."... it is true 99% of the time... but not always. The one example that comes to mind is a binary search of an array. You can keep calling your binary search function recursively on successively smaller subsets of the array, or you can just overwrite the variables that specify the bounds of the search and iterate. In this case, the recursive solution looks cleaner, but the extra info on the stack (the previous bounds of the search) is actually totally redundant.

Share this post


Link to post
Share on other sites
NeRo    122
Does anyone know of any resorces about the mechanical removal of recursion? i.e. how to turn general recursive algorithm x into iterative algorithm y.

Share this post


Link to post
Share on other sites
Semiel    122
Recursion enables a rather intuitive (but it needs alot of training to think recursive) solution to complex problems, f.ex. binary trees, pattern matching (AI)...

Those 2 examples are quite easily implemented using recursion while the iterative solution is not *quite* as fast. As those things are inherently recursive (think fractals) its only logical to implement it that way.

Where performance is not an issue, recursion often seems the more elegant solution.

I dont think you can generally transform in a mechanic way recursion into iteration. I think i remember that every recursion *can* be transformed into iteration though (although it might be very hard).

There is one form of recursion that can be transformed automatically though. Its called "tail recursion" and can be replaced by an iterative loop. Its when there are no more operations after the recursive function call.

Look up the key words "iteration tail recursion optimisation" and you will find what you need...

Further there are languages that do not support iteration... Ah the fun

[Oh, and someone said that the iterative method is always faster. I read somewhere that the "optimised" iterative conversion of recursion might end up actually slower than the original]

Have fun,
Semiel.



Edited by - Semiel on August 7, 2000 4:46:46 PM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Here is the simplest recursive and iterative solutions to a problem that I know. The problem is to free a linked list. I''ll use C just because I feel like it.

Here is the structure for the linked list.


typedef struct lnklst
{
void *data;
struct lnklst *next;
} LnkLst;


First the more typical iterative solution that frees node from the start to the end of the list.


void freeList(LIST *head)
{
LnkLst *tmp;

while(head != NULL)
{
tmp = head -> next;
free(head); // heh heh
head = tmp;
}
}


And now the recursive which frees nodes from the end to the start of the list.


void freeList(LIST *node)
{
if(node -> next != NULL)
{
freeList(node -> next);
}
free(node);
}


(I hope I got that all right, but you get the point )

Mike Roberts
aka milo
mlbobs@telocity.com

Share this post


Link to post
Share on other sites
milo    122
Ack!

The LIST in there once or twice is supposed to be LnkLst.

Ack! Phtttp!

And damn that Anonymous dude.

Mike Roberts
aka milo
mlbobs@telocity.com

Share this post


Link to post
Share on other sites
milo    122
quote:

Original post by Kylotan
And as for this statement from Milo: "After all, an iterative solution to a recursive problem essentially comes down to writing your own specialized stack." ... it is true 99% of the time... but not always. The one example that comes to mind is a binary search of an array. You can keep calling your binary search function recursively on successively smaller subsets of the array, or you can just overwrite the variables that specify the bounds of the search and iterate. In this case, the recursive solution looks cleaner, but the extra info on the stack (the previous bounds of the search) is actually totally redundant.



Your right there Kylo. Recursion that does not need to unroll the function calls (i.e. a search) does not really involve writing a ''stack''. However, most recursive solutions unroll the calls to solve the problem.

Mike Roberts
aka milo
mlbobs@telocity.com

Share this post


Link to post
Share on other sites
Belandrew    122
Egad, I wrote a nice paper on recursion a while back for my discrete math class. In general, it''s actually very easy to decide when to use recursion. If the nature of the data is easily dealt with using recursion, then do so. IE, if you''re using a recursive data structure (trees are a natural one), you''ll probably be using recursion. Then, if the recursive solution proves to be too slow (which is only sometimes the case, profile to see if that''s the problem), find an iterative solution to it. And yes, *every* problem that can be solved with recursion can be solved with iteration, although often the recursive solution is much easier to understand.
If you''re using a tail-recursion problem (which means you do any processing before the recursive call, hence the recursion is at the tail), converting it to an iterative solution is pretty easy, and in fact good optimizing compilers will often do that conversion for you.
Here''s the basic steps for tail-recursion to iteration:
First, identify an input increment in the recursive function. This would be based on how the argument is changed with every call. Next, derive an incremental version of the function which uses the previous version as its input. Finally, we can then form a completely iterative computation using the incremental version of the function. This will be implemented using a loop structure rather than a recursive call.

Share this post


Link to post
Share on other sites