Stack overflow on recursive function. Not sure how to fix.

Solar2D General Questions/Discussion
#1

For some reason the code below throws a stack overflow error if the else statement gets executed too many times. I am trying to have the scene.targeting function select a target from the objTable passed in the params, but only targets with a .tgtFlag == false are valid selections. If the function selects a target that has a .tgtFlag == true, it recalls the scene.targeting function passing in the same set of params.

The line that breaks is “local theTarget = params.objTable[math.random( 1, #params.objTable )]” but only after “else scene.targeting(params) end” is called several times.

Any help would be greatly appreciated.

  1. function scene.targeting( params ) – Targeting functions
  2. function animateTarget( target )
  3. if target.savedFlag == false then
  4. transition.to( target, {time = 100, y = target.y - 15} )
  5. transition.to( target, {time = 100, delay = 150, y = target.y, onComplete = animateTarget} )
  6. end
  7. end
  8. – something is broken on line 79 or line 84. Getting a stack overflow whene else statement gets executed repeatedly.
  9. local theTarget = params.objTable[math.random( 1, #params.objTable )]
  10. if theTarget.tgtFlag == false then
  11. theTarget.tgtFlag = true
  12. animateTarget(theTarget)
  13. else
  14. scene.targeting(params)
  15. end
  16. end
  17.  
#2

Is the purpose of your recursion simply to keep randomly trying an object from objTable until you find one where the flag is false, and then animate that one?  In that case, you should just use a while loop, not recursion.  (Recursion makes the most sense to use in expressing algorithms where you’re splitting the problem into smaller and smaller parts.  Here, you’re simply trying to do something again and again until you get a value that works – that’s just plain iteration with a loop.)

You should also make sure you check for the case that al of the objects in the table have the flag as true, otherwise the loop (or recursion) would go forever.

A stack overflow essentially means your recursion is going too deep.  That could be for a few reasons.  Suppose there are a lot (say, 10,000) elements in objTable, and most of them have their flag set to true.  Your random picker calls the function again every time it finds one that is true.  Since most are true, the recursion can get deep pretty fast purely because the random picker is getting unlucky.

Another reason, which is my guess of what’s happening, is that your objTable is small (maybe 5-25 elements?), and at some point all of the flags are true.  Once that happens, the recursion will go on forever, because the random picker never finds one where the flag is false, though it keeps on calling the function to try again.

  • Andrew
#3

Is the purpose of your recursion simply to keep randomly trying an object from objTable until you find one where the flag is false, and then animate that one?  In that case, you should just use a while loop, not recursion.  (Recursion makes the most sense to use in expressing algorithms where you’re splitting the problem into smaller and smaller parts.  Here, you’re simply trying to do something again and again until you get a value that works – that’s just plain iteration with a loop.)

You should also make sure you check for the case that al of the objects in the table have the flag as true, otherwise the loop (or recursion) would go forever.

A stack overflow essentially means your recursion is going too deep.  That could be for a few reasons.  Suppose there are a lot (say, 10,000) elements in objTable, and most of them have their flag set to true.  Your random picker calls the function again every time it finds one that is true.  Since most are true, the recursion can get deep pretty fast purely because the random picker is getting unlucky.

Another reason, which is my guess of what’s happening, is that your objTable is small (maybe 5-25 elements?), and at some point all of the flags are true.  Once that happens, the recursion will go on forever, because the random picker never finds one where the flag is false, though it keeps on calling the function to try again.

  • Andrew