Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Replacing recursion

 
Mr. C Lamont Gilbert
Ranch Hand
Posts: 1170
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is there a strategy or pattern to replace recursive calls of a function?
 
Scott Ambler
author
Ranch Hand
Posts: 608
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I guess you'd need to turn the recursive calls into some form of loop.

Why would you want to do this?

-Scott
 
Frank Carver
Sheriff
Posts: 6920
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Mr. C Lamont Gilbert
Ranch Hand
Posts: 1170
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic