stairwayoflight
January 11th, 2009, 11:53 PM
Hello,
I am looking for tips to make a recursive function yield an iterative process and use constant resources in Java.
I wrote a mult-recursion program several times over, and each time it produced a stack overflow. I will describe it briefly in concept, but as I am not so much interested in getting it to work, I won't paste the actual code.
Assuming I want to recursively search through many possible solutions to find a "best" answer (eg. "backtrack" search I believe it is called), are there any "gotchas" to be aware of? I was thinking of a "stack" of choices of size 400, and a word list of arbitrary length (which would not change).
Thanks,
Stairwayoflight
For those interested:
In concept, the program keeps track of words that have been "chosen" as part of the solution. To add a word to the solution it is pushed onto the "stack" of choices; to backtrack it is "popped" and the state is incremented so the word is not tried in the same way.
At first I thought to avoid the overflow I simply had to avoid instantiating or changing the size of objects in (or as a result of) my recursive function, so I wrote that stuff out. Then someone told me passing primative types like int results in a *copy*, and so I took those out. I simulated the "stack" so I wouldn't have to have my ArrayList grow or shrink.
My program was intended to do an exhaustive search of all the possible crosswords which could be generated with a given word list. I had two ArrayList objects: one being the word list, the other being a simulated "stack" of choices.
I am looking for tips to make a recursive function yield an iterative process and use constant resources in Java.
I wrote a mult-recursion program several times over, and each time it produced a stack overflow. I will describe it briefly in concept, but as I am not so much interested in getting it to work, I won't paste the actual code.
Assuming I want to recursively search through many possible solutions to find a "best" answer (eg. "backtrack" search I believe it is called), are there any "gotchas" to be aware of? I was thinking of a "stack" of choices of size 400, and a word list of arbitrary length (which would not change).
Thanks,
Stairwayoflight
For those interested:
In concept, the program keeps track of words that have been "chosen" as part of the solution. To add a word to the solution it is pushed onto the "stack" of choices; to backtrack it is "popped" and the state is incremented so the word is not tried in the same way.
At first I thought to avoid the overflow I simply had to avoid instantiating or changing the size of objects in (or as a result of) my recursive function, so I wrote that stuff out. Then someone told me passing primative types like int results in a *copy*, and so I took those out. I simulated the "stack" so I wouldn't have to have my ArrayList grow or shrink.
My program was intended to do an exhaustive search of all the possible crosswords which could be generated with a given word list. I had two ArrayList objects: one being the word list, the other being a simulated "stack" of choices.