#### Archived

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

# 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 on other sites
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 anempty 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 stackwith useless data, and I have to guard aginst dereferenceing a NULL pointer. It''s something that comes with experiance, but finding a goodrecusive solution to something is one of the more fun thingsyou can do at a computer while typeing with both hands.-- Grib 
 0 
 Share this post Link to post Share on other sites 
 
 
 Stoffel    250 Stoffel    250 Contributor Members 250 2538 posts Report post Posted July 25, 2000 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. 0 Share this post Link to post Share on other sites dj9781    122 dj9781    122 Member Members 122 40 posts Report post Posted July 26, 2000 Im not positive if it''s true or not but someone once told me a portal engine uses recursion. 0 Share this post Link to post Share on other sites Ionut Costica    122 Ionut Costica    122 Member Members 122 74 posts Report post Posted July 26, 2000 Recursion can be used for some functions: { 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. 0 Share this post Link to post Share on other sites milo    122 milo    122 Member Members 122 131 posts Report post Posted July 26, 2000 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 Robertsaka milomlbobs@telocity.com 0 Share this post Link to post Share on other sites Ionut Costica    122 Ionut Costica    122 Member Members 122 74 posts Report post Posted July 26, 2000 Here''s an example:(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. 0 Share this post Link to post Share on other sites Stoffel    250 Stoffel    250 Contributor Members 250 2538 posts Report post Posted July 26, 2000 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. 0 Share this post Link to post Share on other sites bishop_pass    109 bishop_pass    109 GDNet+ Members 109 9309 posts Report post Posted July 26, 2000 Recursion solves:maze navigationbranching problemsoctreesfractal generationAI problem solvingbintreesray tracingportal enginesgeneration of plant formscalculation of problems which rely on solutions from sub-problemsroot findinglanguage interpretationlanguage compilationnatural language parsinghierarchical radiosityIf 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. 0 Share this post Link to post Share on other sites Ionut Costica    122 Ionut Costica    122 Member Members 122 74 posts Report post Posted July 26, 2000 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. 0 Share this post Link to post Share on other sites Krinkle    122 Krinkle    122 Member Members 122 10 posts Report post Posted July 26, 2000 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! 0 Share this post Link to post Share on other sites Krinkle    122 Krinkle    122 Member Members 122 10 posts Report post Posted July 26, 2000 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! 0 Share this post Link to post Share on other sites Kylotan    10007 Kylotan    10007 Moderator - Scripting Languages and Game Mods Moderators 10007 14014 posts kylotan 2213 pixels Report post Posted August 7, 2000 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. 0 Share this post Link to post Share on other sites NeRo    122 NeRo    122 Member Members 122 23 posts Report post Posted August 7, 2000 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. 0 Share this post Link to post Share on other sites Semiel    122 Semiel    122 Newbie Members 122 3 posts Report post Posted August 7, 2000 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 0 Share this post Link to post Share on other sites Guest Anonymous Poster    Guest Anonymous Poster    Guests Report post Posted August 7, 2000 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 Robertsaka milomlbobs@telocity.com 0 Share this post Link to post Share on other sites milo    122 milo    122 Member Members 122 131 posts Report post Posted August 7, 2000 Ack!The LIST in there once or twice is supposed to be LnkLst. Ack! Phtttp!And damn that Anonymous dude. Mike Robertsaka milomlbobs@telocity.com 0 Share this post Link to post Share on other sites milo    122 milo    122 Member Members 122 131 posts Report post Posted August 7, 2000 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 Robertsaka milomlbobs@telocity.com 0 Share this post Link to post Share on other sites Belandrew    122 Belandrew    122 Member Members 122 42 posts Report post Posted August 8, 2000 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. 0 Share this post Link to post Share on other sites ncsu121978    1344 ncsu121978    1344 Contributor Members 1344 1372 posts 11 pixels Report post Posted August 8, 2000 when: only if your teacher says towhy: i have no idea why somebody would use recursionlooks pretty, makes you look smarter, but it is crap "Now go away or I shall taunt you a second time" - Monty Python and the Holy GrailthemGames Productions 0 Share this post Link to post Share on other sites 
 
 Go To Topic Listing General and Gameplay Programming 
 GameDev Unboxed 0 Indie Marketing For N00bs: Lesson 3 - Make The News, Be The News By Jesse "Chime" Collins 0 Nintendo's Nindies Showcase Rundown By Jesse "Chime" Collins 0 Gamescom 2017 News Round-Up By Jesse "Chime" Collins View more Latest Images 0 1 0 0 0 0 0 0 0 View more Popular Now 24 Cache Coherency and Object Update By AxeGuywithanAxeStarted 14 hours ago 13 C++ Player out of tile map By DKdowneRStarted 22 hours ago 28 Will we ever see an adoption of something other than C and C++? By Alpha_ProgDesStarted Wednesday at 01:59 PM 10 Fixed update in game loop By matt77hiasStarted Tuesday at 07:21 PM 13 What languages should a person learn to be a well-rounded programmer? By Alpha_ProgDesStarted Tuesday at 06:16 PM GDNet Discord Chat All Activity Home Forums Programming General and Gameplay Programming When and Why Recursion