How to avoid stack overflow with recursion?
(1) Use tail-end recursion: that allows you to work on linear structures without additional stack requirements. Doing explicit tail-end recursion can be seen as converting the recursion into an iteration [see sample code]. (2) On non-linear structures [e.g. balanced trees] take the shorter route first [and the rest as tail-end recursion]: that will cut the recursion depth to less than log2 of the input size. Such a small recursion depth will likely not produce an overflow. Sample: reasonable quick sort implementations. It might not be so easy to recognize the shortest path [as it is with quick sort; consider the problem of finding a way out of a labyrinth solved by backtracking: at each step you don’t know in advance which direction will conceal the longest path]. (3) If one can figure out a reasonable upper limit for log2 of the problem size, that can be used to limit the search depth: if that limit is reached, give up and try (all) other branches first; performance will suffer and ma
