0

I used to think iterative algorithms be always superior to recursive ones due to the potential stack overflow issue, as long as one doesn't mind the extra efforts on coding. Therefore, if I were to build a util function to be used over and over again, I should always go with iterative. Is that logic correct? Or is there any standard trick to avoid stack overflow in recursive even for very large N? Still assume the data structure itself is not too big to fit in RAM.

Indominus
  • 1,228
  • 15
  • 31
  • Assuming you're doing some incredibly deep recursion, you could write a tail-recursive function and hope for [tail call optimization](https://stackoverflow.com/questions/310974/what-is-tail-call-optimization) – Ryan Haining Dec 06 '18 at 01:06
  • every recursion could be changed into the loop, but it would still require an extra space (unless it's a tailed one) so at the end you would still have the same space complexity – mangusta Dec 06 '18 at 01:49
  • It's common to use a `Stack` object and a loop instead of a recursive call. – Matthew Watson Dec 06 '18 at 09:52

1 Answers1

0

Basically you're right for common compilers iteration is superior in both memory consumption and performance, but do not forget there are languages usually focused on functional programing and or AI that are optimized for recursion and with them the recursion is superior instead...

Anyway if I can I always use iteration for the reasons you mentioned. However recursive approach is often more simplistic than iterative one and the amount of coding required to convert to iteration is too much... In such cases you can do these:

  1. limit heap/stack trashing

    simply get rid of as much operands, return values and local variables as you can as each recursion will make a copy/instance of it...

    you can use static variables for the locals or even global ones for the operands but beware not to break the functionality by using this.

    You would not believe how many times I saw passing array as operand into recursion ...

  2. limit recursion

    if you got multi split recursion (one recursive layer have more than 1 recursive call) then you can have some internal global counter how many recursions are currently active ... if you hit some threshold value do not use recursive calls anymore ... instead schedule them into some global array/list IIRC called priority queue and once all the pended recursions stop process this queue until its empty. However this approach is not always applicable. Nice examples for this approach are: Flood Fill, grid A* path finding,...

  3. increase heap/stack size

    executables have a table that tells the OS how much memory to allocate for its parts... so just find the settings in your compiler/linker/IDE and set the value to reasonable size.

I am sure there are more techniques but these are those I use ...

Spektre
  • 49,595
  • 11
  • 110
  • 380