1. 22
    1. 11

      I agree that naturally recursive data types are probably the best way to teach recursion, but I disagree with the dismissal of the other examples because they “aren’t used in the real world.” This is a really silly argument— a “hello world” program is utterly useless in the real world but still is useful pedagogically.

      1. 6

        The fibonacci and factorial examples also have pedagogical value especially when recrusion is being presented alongside concepts in discrete math. Both give way to simple properties which can be proved easily with mathematical induction, and induction is very useful when it comes to actually proving that recursive algorithms are correct.

      2. 4

        a “hello world” program is utterly useless in the real world but still is useful pedagogically.

        um I’m not sure that I agree, I print strings to stdout pretty often, but I’ve never ever needed to compute a fibonacci number for anything

        1. 2

          You print strings to stdout, but do you print the string “hello world” to stdout? Or was the hello world program a nice way to teach you printing that was unrelated to real-world applications? One of the other classic pedagogical programs students have to write is a choose-your-own-adventure (teaching branching), yet I am not a VN developer. Was this a bad program to have me write?

          1. 3

            I view the hello world program as a way to get students (or programmers) familiar with the tools of the trade (or a new platform).

        2. 1

          I print strings to stdout pretty often

          Yes, just as people use recursion pretty often; you’re missing the point.

          You should be consistent in how generally you look at each example program.

          Nobody applies printing in the real world to print only static values in the whole program, just as nobody applies recursion in the real world to fibonacci, but you’re looking at the generalities of hello world and the particulars of recursive fibonacci.

          Both apply techniques that are used in the “real world”, even if the way they’re applied isn’t done in the real world. You can’t say, “but I do print values”, but then attack the fibonacci program when people do use recursion, which is what it’s demonstrating, not fibonacci itself, just as the hello world program isn’t demonstrating how to print the specific value, “Hello, world!”.

    2. 1

      I believe that many beginners struggle with recursion not because the task at hand is not practical enough, but because the concept of recursion is difficult to visualize and therefore to model in one’s head. Especially when implemented with functions. Functions calling other functions already introduce nontrivial amount of unintuitiveness and complexity. Functions calling themselves is just weird and difficult.

      My attempt to explain recursion is based on a visual language of analogies to function definitions, function calls and values: https://youtu.be/vLhHyGTkjCs

    3. [Comment removed by author]

      1. 3

        To be honest, recursion clicked for me reading Erlang/Elixir. That’s how you handle event loops, state, etc. For example (extremely simplified):

        def dictionary_service(state, message) do
          case message do
            {:get, sender, key} ->
                sender ! Map.get(state, key)
            {:set, _sender, key, value} ->
                Map.put(state, key, value)

        The problem is I don’t do as much recursion as I’d like - I don’t want to blow out the stack in C, a world without TCO…

        1. 1

          In C you can (but probably shouldn’t) use static variable init within a function for this, as long as it’s used carefully.

        2. 1

          Gcc and clang supports this optimisation.

        3. 1

          I also finally realised that recursion was useful when I was learning Elixir.

          The moment I decided I liked it was when saw that I could write reduce with it, with even easier to read and understand (for me) code than the good old reduce function I was used to using in various languages.

          1. 1

            It’s not just recursion, but the bits like proper pattern matching that make it natural and desirable to use over for-and-if.

    4. [Comment removed by author]