Recursion finally clicked for me after learning induction where you assume you already have a working solution for all cases below n and your only job is to implement the nth case
I remember figuring out by myself the reclusive solution to tower of Hanoi back in high school AP comp sci class as extra credit. It was a shock that the solution is so simple and elegant.
Wow this is beautiful. I love it when a complicated process can be simplified into such logical steps, that you know work in isolation, so you know the strategy will also work overall. Thx for sharing!
Fascinating how many of these comments are about recursion. My mind was blown when I realized that recursion is almost never the right solution in practical applications due to memory and stack exhaustion concerns (and that introductory CS/programming courses usually do a disservice to students by treating it as a core concept without mentioning that caveat).
My mind is always blown by the tiny demoscene demos.
TCO is not supported in most languages that are practical for large scale software engineering projects today. It's also not applicable in many recursion scenarios that they teach in school.
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.
I see your point about education. Everything has its place and a for loop can sometimes be easier to read. But some algorithms are more naturally expressed recursively.
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).
The only time I've ever ran into a stack limitation was real-time embedded systems with a tiny stack.
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.
- 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!"