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!

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!

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.

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.

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

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

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

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

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.

when: only if your teacher says to
why: i have no idea why somebody would use recursion

looks 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 Grail
themGames Productions