File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes OO, Patterns, UML and Refactoring and the fly likes Replacing recursion Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Engineering » OO, Patterns, UML and Refactoring
Bookmark "Replacing recursion" Watch "Replacing recursion" New topic
Author

Replacing recursion

Mr. C Lamont Gilbert
Ranch Hand

Joined: Oct 05, 2001
Posts: 1170

Is there a strategy or pattern to replace recursive calls of a function?
Scott Ambler
author
Ranch Hand

Joined: Dec 12, 2003
Posts: 608
I guess you'd need to turn the recursive calls into some form of loop.

Why would you want to do this?

-Scott


<a href="http://www-306.ibm.com/software/rational/bios/ambler.html" target="_blank" rel="nofollow">Scott W. Ambler</a><br />Practice Leader Agile Development, IBM Rational<br /> <br />Now available: <a href="http://www.ambysoft.com/books/refactoringDatabases.html" target="_blank" rel="nofollow">Refactoring Databases: Evolutionary Database Design</a>
Frank Carver
Sheriff

Joined: Jan 07, 1999
Posts: 6920
I've seen this done a few times, but only usually either in languages that don't properly support recursion or as college assignments.

The trick is to keep a stack to hold transient data, then loop round either pushing something on to the stack to simulate entering a recursive call, or popping something off the stack to simulate returning from a recursive call. When the stack is eventually empty, it's probably a good idea to stop the loop.

I have to echo Scott, though. I'm intrigued as to what you need this for.


Read about me at frankcarver.me ~ Raspberry Alpha Omega ~ Frank's Punchbarrel Blog
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
This comes up in languages that don't support recursion. I did it exactly once in COBOL. I put all of what we'd consider "local variables" into a structure and made an array of structures. Doing recursion just meant incrementing the array index and using the next structure. Returning a value meant grabbing a value from the current index before decrementing the index. COBOL arrays are fixed size so it's easy to run out of "stack space."

This could be an interesting learning experience in Java, but I wouldn't bother to convert a truly recursive algorithm to loops outside of an exercise. On the other hand, somebody on my team wrote what should have been a loop as recursion, I suspect because he couldn't figure out a simple way to express the terminating condition in a while clause. I might turn that one into a loop if I ever open up the class again.


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Mr. C Lamont Gilbert
Ranch Hand

Joined: Oct 05, 2001
Posts: 1170

I dreamed up the solution while I was sleep last night I really need to take a break from java, maybe read a good book or something again. I like fantasy and DnD.

Anyway, yea simulating the stack was my solution. I used a LinkedList and a while loop. Fixed it up nicely. I wanted to do this so as to not run out of stack space since I am doing a pathing algorithm that will enter the method once for each link in the path. That can get pretty deep. Though there are only a few variables required in the method.

Turns out its tail recursion too if I understand the term correctly.
 
Consider Paul's rocket mass heater.
 
subject: Replacing recursion