|
|
Back to UserFriendly Strip Comments Index
|
recursive -> iterative | by dennismv | 2004-12-21 02:24:43 |
|
Umm... | by MaW | 2004-12-21 02:34:25 |
| supposedly |
by dennismv |
2004-12-21 02:51:42 |
when you use recursion, the compiler, the runtime system and the system's stack convert the recursion to iteration for you.
However, you pay the price of the stack calls and extra variable generation that you don't have exact control over.
So what you can do is create your own stack, and save your own variables in the stack.
I have a program where I did that -- created my own stack to do the iteratin, and for some reason the program actually ran slower than the recursive version. I guess compiler's stack version or optimization techniques were more efficient than mine.
Also, my program is a backtracking algorithm. In the recursive function, I do not save all the variables -- one array has values added to it and removed from it as recursion goes a level up or down. When I converted the recursive function from that algorithm to an iterative one, I could not get it to work without saving that array on the stack.
Thus, when I save the array explicitly on the stack in the iterative version, the program works fine. When I don't save it, and try to update it manually, the program breaks down. I could not find a way yet to get it to work.
The recursive function does not save the array, and updates it manually. Thus, I wonder if it's possible to always convert an iterative version to be functionally identical to the iterative one.
Thus, the answer to can you always convert a recursive function to iterative is probably yes.
But the question "can you convert a recursive function to iterative, so that the functionality remains strictly the same" ... so far is undetermined. |
|
[ Reply ] |
|
|
[Todays Cartoon Discussion]
[News Index]
|
|
