7 ms·

I was mind blown in college when learning recursive programming and being introduced to the recursive solution to the Tower of Hanoi problem: - https://en.wiki

by tcgv 4y ago

I was mind blown in college when learning recursive programming and being introduced to the recursive solution to the Tower of Hanoi problem: - https://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_implementation 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!"

cyclotron3k 4y ago
I had the exact same experience too. Really blew my mind.
ivansavz 4y ago
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!
panda88888 4y ago
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.
trinovantes 4y ago
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
ak217 4y ago
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.
- nequo 4y ago
  > never the right solution in practical applications due to memory and stack exhaustion This is not true with a good compiler that does, e.g., tail call optimization, or is it?
  - ak217 4y ago
    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.
    - nequo 4y ago
      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). [1] https://v2.ocaml.org/manual/tail_mod_cons.html https://v2.ocaml.org/manual/tail_mod_cons.html [2] https://www.scala-lang.org/api/2.12.1/scala/annotation/tailrec.html https://www.scala-lang.org/api/2.12.1/scala/annotation/tailr...
      - 4y ago

by tcgv 4y ago

cyclotron3k 4y ago

I had the exact same experience too. Really blew my mind.

ivansavz 4y ago

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!

panda88888 4y ago

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.

trinovantes 4y ago

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

ak217 4y ago

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.

nequo 4y ago
> never the right solution in practical applications due to memory and stack exhaustion This is not true with a good compiler that does, e.g., tail call optimization, or is it?
- ak217 4y ago
  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.
  - nequo 4y ago
    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). [1] https://v2.ocaml.org/manual/tail_mod_cons.html https://v2.ocaml.org/manual/tail_mod_cons.html [2] https://www.scala-lang.org/api/2.12.1/scala/annotation/tailrec.html https://www.scala-lang.org/api/2.12.1/scala/annotation/tailr...
    - 4y ago