3 ms·
I learned about stack based programming when I bought a HP28s calculator in 1988. It could be programmed in its Forth like language, had data structures like li
by submeta 4y ago
I learned about stack based programming when I bought a HP28s calculator in 1988. It could be programmed in its Forth like language, had data structures like lists, arrays, matrices, and symbols. It was also my intro to Scheme. It was like revelation. When everyone else around me was learning C or Pascal, where arrays had fixed lengths, I had seen the future with dynamic data structures. I could implement and test ideas that would take me ten or a hundred times more LOC.
Now over 30 years later I still use a stack to implement tree traversal instead of using recursion.
- zozbot234 4y ago> Now over 30 years later I still use a stack to implement tree traversal instead of using recursion. Recursion is the same as "using a stack". It's just using the system stack generally, which might not be what you want.
- submeta 4y agoBut it is possible to get a stack overflow error when using recursion to implement tree traversal if the depth of the tree is too large or if the recursion is not properly managed. Implementing tree traversal iteratively can help avoid that because it does not rely on recursive function calls that can build up on the call stack. Instead, an iterative approach uses an explicit data structure (such as a stack or queue).
- skybrian 4y agoWell, you could run out of memory implementing a stack as an array too. It all depends on what the limits are.
- roflyear 4y agoI kind of like that because if your tree depth is that large you're throwing away the benefits of a tree generally and that is an indication you should be doing something different.