3 ms·
You can just replace the call stack with an explicit stack in your function – that should never be hard, just a bit less readable :).
by chronial 9y ago
You can just replace the call stack with an explicit stack in your function – that should never be hard, just a bit less readable :).
- scardine 9y agoCan you use some structure like a clojure zipper[1] for traversing trees iteratively? [1] http://josf.info/blog/2014/03/21/getting-acquainted-with-clojure-zippers/ http://josf.info/blog/2014/03/21/getting-acquainted-with-clo...
- odonnellryan 9y agoYes I can see how this makes sense, but I wouldn't say it is easier than recursion! Maybe a good exercise, but when traversing a tree the recursive solution is very easy to understand. The iterate solution ... Then you have other problems, where the recursive solution is actually not super easy to understand why it "works" immediately (think, balanced paren generation) and going on to create an iterative solution, while not insanely hard, is not something super obvious.... what's your condition to stop iteration, again? Maybe I'm thinking about that the wrong way, I'd love to learn more about it! That problem is closely related to tree traversal, anyway, I should fool around with those two ideas a bit more to properly understand.
- arghwhat 9y agoI never said it was easier, I just said it was not much harder. :) Like I said, it is sometimes a bit less readable (tree-walking is a good example of such case), but at the same time, what the code actually does is much clearer. You have no hidden costs, and the code is easier to optimize this way. You mention a case where you do not fully understand why the recursive solution works, in which case you obviously can't easily write an iterative solution. However, in this case, you are poorly equipped to make any implementation, recursive or iterative.