- https://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_imple...
I remeber thinking "where's the rest of the code? It surely can't be just those lines!"
My mind is always blown by the tiny demoscene demos.
This is not true with a good compiler that does, e.g., tail call optimization, or is it?
Even in languages where TCO is supported, it's usually not safe to rely on from an engineer's perspective because there is usually no way to reliably assert that TCO is actually applied to any given function.
And again, when they teach recursion in school, they don't normally tell you that it can be unsafe unless your compiler happens to apply TCO or your language explicitly supports tail recursion.
A lot of languages do support TCO. For example, Scala (used by Twitter), OCaml (used by Jane Street for everything, used as the host language for Coq, originally used to implement the Rust compiler), Kotlin, Haskell, Clojure, Lua (used as an embedded language in many places), Elixir, Perl. Not necessarily your popular bread and butter languages but definitely used in production and available if necessary.
Your point that it is generally difficult to know whether TCO is applied is also well-taken. But in OCaml, you can annotate the recursive function call with `[@tailcall]` to verify that the compiler performs TCO.[1] Likewise, you can annotate your functions in Scala.[2] In languages without such annotations, one can get a sense by memory profiling (possibly not emphasized enough in those intro CS courses).
[1] https://v2.ocaml.org/manual/tail_mod_cons.html
[2] https://www.scala-lang.org/api/2.12.1/scala/annotation/tailr...
For modern computers/tablets I have never experienced an issue. Granted, what really matters is your data/recursion level, but even hundreds of recursive calls are not a problem for most applications.
Recursive solutions are usually so much easier to understand than stack/array based looping solutions that they are my go to for things like tree traversals or searching.
A very subjective statement. Yes, your data matters. Also, the scale and security model/trust boundary of your application matters.
Some actual problems with recursion based algorithms:
* They will break unexpectedly as you scale them up.
* They are not memory efficient, so you won't be able to process much in parallel if your data is non-trivial.
* They can make your service trivially DoSable, so now you have to worry about either sanitizing your input or monitoring your stack instead of just timeouts/rate limits.
I've lost track of the number of times I've had to tweak JVM settings, write up security issues, or just straight up tell people things won't work because an academic researcher decided to implement an algorithm with recursion, and then engineers were asked to productize it.