Take Away Lesson
Even though problems like Towers of Hanoi
are naturally recursive problems with easy implementations using recursion, I still advise you to do their final implementation in languages like Java, C++ etc. using the iterative technique.
This way only one activation record would be pushed on the stack for the iterative function. However, when given such problems, always write the recursive mathematical expression or recursive pseudo-code for them, and then figure out how to implement them iteratively.
Iterative
functions would be faster and more efficient compared to their recursive counterparts because of of the lack of activation stack
overhead.
Some functional programming languages like LISP
have built in techniques to handle tail recursion without building a large activation stack. They are pretty cool, in the sense that they allow you to code everything using recursion
, without the extra overhead of activation stack.
I hope you enjoyed this lesson as much as I enjoyed creating it.