On Learning Recursion

A question on quora got me thinking about how bad we computer scientists teach recursion.

I claim programmers work day to day in environments that use recursive thinking, so understanding recursion is very important stuff.

We can easily try to teach things like fractals, hanoi, fibonacci, tri-ominos, factorials, and more. These are all nice and beautiful mathematical facts/puzzles, but they are bullshit and I don't think they help teach recursion. I claim they are bullshit because they are too nice of results and they don't show any scaffolding involved in how they were constructed or why it is that way.

Recursion ultimately boils down to "If I can do something on something smaller and I can combine smaller things into the bigger result, then I can compute on things that are huge."

It is a powerful tool, and I think the best way to learn and master recursion is to write a programming language. When you understand how a programming language works, then I further claim you will produce a lot less bugs and have a greater understanding of what your code is doing.

Recursion is akin to mathematical induction in the form of structural induction. Problematically, if you take a computer science course, then you will start with the math. While this is great in theory, most people have a shaky and incomplete foundation in mathematics. So, the mathematical approach to teaching recursion isn't going to be a wild success. I claim that a good understanding of recursion enables people to be more effective in functional programming (and thus programming in general).

Having complained and made many wild claims, I started a github repo on teaching recursion by writing a simple computational language which I may extend in the future. For now, it provides a simple parser and an eval() function and how to use it to write a graphing calculator. Each branch in the repo is a stopping point with the master branch containing the final lesson. It has 3 lessons now which give me a warm fuzzy feeling on the inside.

Update: check out Structure and Interpretation of Computer Programs if you are serious about learning how to write a programming language. I'm just a hack when compared to the authors of that great book.