Understanding Recursion as an Absolute Beginner

> Recursive language is a relatively recent phenomenon

Is there any evidence it's more recent than non-recursive language acquisition, evolutionarily (rather than developmentally ie child to adult)?

For reference for others in this thread, an example of linguistic recursion is <https://en.wikipedia.org /wiki/This_Is_the_House_That_Jack_Built>

    This is the horse and the hound and the horn
    That belonged to the farmer sowing his corn
    That kept the rooster that crowed in the morn
    That woke the judge all shaven and shorn
    That married the man all tattered and torn
    That kissed the maiden all forlorn
    That milked the cow with the crumpled horn
    That tossed the dog that worried the cat
    That killed the rat that ate the malt
    That lay in the house that Jack built.

    function countDownFrom(n) {
      console.log(n)
    
      if (n > 0) {
        countDownFrom(n - 1)
      }
    }

This would also make it simple to add a `step` argument, which could be written as:

    function countDownFrom (n, step) {
      console.log(n)
    
      if (n > 0) {
        countDownFrom(n - step, step)
      }
    }

1. Write down what your function does in a comment. (e.g., "sum all the elements of a binary tree"). 2. Write the function signature. 3. Write the base case. (This is usually straightforward and most people don't seem to have an issue with it when reminded.) 4. Stop thinking. 5. Assume your function already works and write the recursive case. 6. Profit!

I find where most people get confused over recursion is in trying to reason about the recursive case. They think "Well if I start at the root of the tree, then the next thing I need is to get the children... and then... with the first child... uh..."

They get lost in the recursion. So I tell them: assume your function already works. Trust that you will write it correctly eventually. What does your function do? How can you use that?

If you assume you already have a function that sums binary trees, and if you're trying to sum the children of a branch node, well then use that function that you already have to get the sum of each of those children trees, and add up the results!

I always recommend to never try to visualize N levels of recursion, unless you're working through an example to actually test your implementation. Worrying about the deeper recursion is how people get lost and confused. Keep it simple: just look at the one layer and assume the other layers will do their job correctly.

Any recursive solution can be turned into an iterative solution if you store the arguments of the recursive function in a data structure on the heap, and turn the recursive call itself into an access/modification of the data structure. As a specific example, any tail-recursive function can be turned into a for loop that modifies a stack. Recursive functions that are not tail-recursive (such as fibonacci) will require more complex data structures, depending on their internal recursive structure. (fibonacci can use an indexable list, for instance).

This is the heart of memoization and dynamic programming.

I actually think this is not a good way to understand recursion. It's like saying "once you think of the lambda calculus as another way to build a Turing machine, it immediately is demystified." Yes, it's true that they're equally powerful, but their differences are what make one or the other more suitable to certain circumstances.

I think with recursion the best way to show this distinction is to look at navigation over a recursive structure, like a binary tree. You could implement any navigation over a binary tree with some nice loops, but they don't really mean anything in relation to the program: they're just a procedure to get the job done.

On the other hand, since binary trees are recursively defined (each node is either a leaf containing data or a branch containing two binary trees), using structural recursion to navigate the tree is significantly more straightforward than any looping construct. This is made super clear in a language like Haskell:

    data BTree
      = Leaf Int
      | Branch Int BTree BTree
    
    sumTree :: BTree -> Int
    sumTree (Leaf v) = v
    sumTree (Branch v l r) = v + (sumTree l) + (sumTree r)

    @dataclass
    class BTree: pass
    
    @dataclass
    class Leaf(BTree):
      v: int
    
    @dataclass
    class Branch(BTree):
      v: int
      l: BTree
      r: BTree
    
    def sum_tree(t: BTree) -> int:
      stack = [t]
      total = 0
      while stack:
        curr = stack.pop()
        if isinstance(curr, Leaf):
          total += curr.v
        elif isinstance(curr, Branch):
          total += curr.v
          stack.append(curr.l)
          stack.append(curr.r)
        else:
          raise RuntimeError("Invalid BTree subclass.)
      return total

In contrast, the Haskell solution is clearly correct at a glance, I think. Ignoring the difference in length of code, the Haskell is clearly recursing over the structure of the tree. This is, in my opinion, significantly easier to reason about than any amount of looping.

I guess the caveat to all this is: recursion is well-suited for certain kinds of problems (such as navigating a recursive datatype), and loops are well-suited for different kinds of problems. But saying "they're equivalent so think of all recursion as loops" is missing the forest for the trees, I think.

However, null==undefined so you might not even notice the difference.

scheduling a health check job recursively. if the health check fails, it schedules itself to run again in X seconds with N-1 runs until giving up and marking the service as down.

iteration here simply wouldn’t work

I've used the same approach recently when I wrote a GraphQL query generator in Swift. I recursively iterate through an array of dictionaries, each being able to also hold an array of dictionaries of it's own, each being able to also hold an array of dictionaries of it's own, and so on. In the end all I end up with is single a string.

Maybe it's not exactly more efficient, but it was certainly much easier for me.

The reason why I wrote it is because of my own personal experience. In my programming class, my friends were having hard time understanding recursion so that was the primary motivation for writing this blog.

I strongly disagree. Many people have never had to reason about recursion so explicitly before going into CS. Just because it's difficult to understand explicitly at first doesn't mean they won't get better.

If they never understand recursion, then that's a problem, but I think that probably says more about the teacher than the student.