Dijkstra was right – recursion should not be difficult

"This task can also be solved using iterative solution, but it’s way more complicated because we would have to nest for loops but don’t know how deep they are nested. The unknown number of nested loops is a common characteristic of all problems that are recursive in their nature and should give you a hint that recursive solution is required."

Would suggest instead something like

"We could solve this directly by managing our own stack of work done and keeping track of where we are in the problems as we divide them up, but it's easier to take advantage of the fact that the programming language is already providing us a call stack that can do this work for us."

Then, later, you can point out that this also helps with the backtracking solution as the programming language is maintaining the old environments; if you were iteratively managing your own stack you'd also have to backtrack manually.

Because that's how you transform a recursive call into an iterative one, not nested for loops. The general points made in the article still hold up, of course.

Recursion shouldn't be difficult, but we write recursive programs using one tool: self-referential functions. That's like trying to write structured programs using one tool - goto.

Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire[1] pioneered generalized recursion schemes and influenced work in Haskell[2] and Scala[3]. It's great having the vocabulary to describe recursion and the tools to elegantly recurse, but anamorphism tends to shut down conversations faster than mentioning the m-word.

[1] - https://maartenfokkinga.github.io/utwente/mmf91m.pdf

[2] - https://hackage.haskell.org/package/recursion-schemes

[3] - https://github.com/slamdata/matryoshka

This article touches on some good points. In particular, the part about trusting that the function will do the right thing is something that people who already understand recursion take for granted but is extremely crucial. However:

"Let's tweak our sum function a a bit: ... That's it."

I really dislike articles that earnestly try to convince the audience that some subject which many find extremely difficult to understand is actually very simple. My impression is that the intent is to help people who lack the confidence to engage with the topic, but in my opinion the exact opposite effect is achieved. At that point in the article, nothing about recursion had been explained and it's not reasonable to expect someone who previously did not understand recursion to read that section and come to the conclusion "that's it!" Instead they'll be sitting there, extremely confused by something which they're being reassured is actually quite simple. This is not going to help their confidence.

So while I appreciate the author's intent, I think that someone who is struggling to understand recursion might leave this article worse off than when they started. And I wish this trope would disappear from tutorials.

You don't really understand how difficult recursion is until you've tried to teach a bunch of programming newcomers the concept. A few get it quickly, but for the rest all the "think of it like ..." suggestions don't really help. It's a concept that everyone seems to have to learn through practice (as the author implies). I fell into the trap that if I only explained it clearly enough I could make it easy for others. Everyone learns it their own way and you just have to give students enough opportunities to practice for them to get it. I don't disagree with Dijkstra that the concept shouldn't be difficult, but I do not believe there are any easy paths to the concept for most.

It's one of the most interesting learning processes in that once you get it, it feels almost as simple as a for loop or simple math. But until you get it it feels like the most opaque, impenetrable wall where 1+1 != 2.

Side note, recursion would be slightly easier if the concept of a base case were applied to all functions as preconditions. The idea of a base case really has more applicability than just in recursion, it's just that we don't call it a base case in other situations.

Recursion is also interesting to implement when doing TDD. It comes in a refactoring step, of course, but you don't have to think about the base case(s) because they've already been done. Again, not suggesting this is helpful to a newcomer struggling, but is just an interesting process.

> This is because a recursive sub-function never solves the exact same problem as the original function, but always a simpler version of an original problem.

This isn't always true. There are plenty of recursive functions whose purpose is merely to climb until a condition is met that there are no more rungs in the ladder.

Recursion is difficult because it isn't just taught, it is mythologized as the potentially infinite source of a one's love for programming. If teachers similarly mythologized the "switch" statement I'm sure they could confuse the topic of conditionals just as easily.

Practice makes perfect, I think most learners can get comfortable with recursion as they use it to implement simple recursive solutions (Fibonacci, tree traversals..etc). Over time it becomes quite natural to recognize when and how to use recursion.

One source of confusion that most learners have stems from the seemingly mysterious way that intermediate results are kept track of. This is one of the downsides of not having experience with low-level programming. If you're familiar with assembly language programming and understand how register contents are pushed/poped on/off the stack between sub-routine calls then it is easier to understand what is happening behind the scenes.

Anything that is self-referential is hard. I remember when we covered proof-by-induction in HS math. There was a significant fraction of the class that did not believe a given proof was sufficient.

If you can't assure yourself of the correctness of a fairly simple recursive function that is given to you, then composing one yourself is going to be nigh impossible.

[edit]

From the article: Instead trust that it returns correct sum for all elements of an array a[i]

This is exactly the point where many people get hung up. They cannot proceed to reading the next line until they understand how the recursive call works. They are unwilling to trust that the function works as advertised, and cannot shift gears to continue past that. In my experience, telling them to "just trust it" and such seems to not help much.

When I was a kid, we learned the principle of mathematical induction in algebra class. That made recursion seem easy.

As for the limitations of recursion on any given system, that's easy to learn because... kids will be kids. Practically the first thing I tried with recursion, ended up with the system operator yelling at me, and learning what a core dump looked like.

If you want to really delve into recursion, I recommend to learn a logic programming language like Prolog.

Interestingly, Prolog programs are often efficient and general because, due to the power of unification, Prolog programs are more often tail recursive than functional programs.

For example, we can define a relation called "append" in Prolog as follows:

    append([], Ls, Ls).
    append([A|As], Ls, [A|Rest]) :-
            append(As, Ls, Rest).

In Prolog, recursion naturally arises by considering the inductive definitions of terms. For example, you can read the second clause as "If it is the case that append(As, Ls, Rest) holds, then it is also the case that append([A|As], Ls, [A|Rest]) holds".

Note that such cases are not naturally tail recursive in Lisp, for example, because in languages that do not support unification of logical variables, there is one additional call of "cons" after the recursive call to construct the result. Also, the Prolog version is much more general and can be used in several directions! For this reason, "append" is not even a good name for such a relation, because it already implies one particular direction.

The two biggest problems with recursion in practical use is that not all compilers can properly handle optimizations around tail calls, and not all TCO capable compilers can handle all tail call cases.

If either case occurs, you run into the issue where you will seemingly randomly blow out your stack space when your list is too long, or your tree too deep. Then you have to fall back to a non-functional idiom (or do some other magical incantations to avoid function stacks, like Clojure's `loop` special form).

I think recursion is a great tool, but it's so poorly implemented in so many languages that it's simply too dangerous to use.

Here are the steps in my recursion experience:

1) teenager reading a pascal book: clueless

2) college C course: imperative "print tree", easy

3) advanced compiler: more sophisticated environment thingies, clueless again

4) CGI quadtrees: want fully recursive solution but chokes

5) rediscovery of lisp: recursion wannabe

6) cons-based lists fundamentals: linear converging recursion is everywhere, pattern is easily understood and memorize, everything makes sense

7) FP and lispy combinatorics (treerec, partition, countdown): it seems like point 2) but something is different now.. deep recursion involves self closing types. It's not just repeat until and do not care about what happens you'll fix it down the road. It HAS to make sense, and to typecheck right away.. recursive steps will be used for the previous level it has to fit logically.

If one reaches that level your understanding shifts entirely. Recursion is it's own solution, it's absurd but it's a deep reference point to solve problems since you can assume something that doesn't exist and see if it holds..

Now you get to rediscover math proofs and a lot of late HS and college math. Finally something I wanted to know and recently found out about, list recursion are only a linear pattern of recurrence. It's one dimensional and often on an easy to proove converging variable (cdr + nil?, natural dec + zero?). There are n-dimensional patterns, and litterature about it. I can't recall the books but I'll dig for it.

And finally, Turing among other tried to rethink imperative programs as one big while modifying one big vector variable (aka system state) and proof that this n-dimensional vector could only have some sound values and would reach terminating ones. (I think it's called linear ranking ..)

Cheers

Some years ago I had problems with recursions too, because I always had some edge cases which made my functions go wild (endless loops). But one day someone told me, that most recursive programs can be written into the skeleton below:

  function a(){
    if(/* Termination Condition */){
      return /* Special Element */
    } else {
      /* Recursion: e.g. a + a */
      return a() + a()
    }
  }

Since that day I love recursions.

I admit this is complete speculation on my part, but I can't imagine it helps to combine recursion with C-style for-loops.

Both pieces of advice from the article: "trust the recursive function" and "don't try and trace the execution" seem easier if the control flow is simpler.

Compare:

    function sum(a) {
        let result = 0;

        for (let i = 0; i < a.length; i++) {
            if (Array.isArray(a[i])) {
                result += sum(a[i])
            } else {
                result += a[i];
            }
        }
        return result;
    } 

    function findCeo(employee) {
        let boss = employee.getBoss();
        if (null == boss) {
            return findCeo(boss);
        }
        else {
            return employee;
        }
    }

The first problem in the OP is ill-typed, so if this was intended to help people get a good grasp on recursion, that may be counterproductive.

I never had any problem using recursion, but my ability to reason about it at an abstract level is due in large part to the excellent paper "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire", which covers various abstract approaches to dealing with recursion schemes. https://maartenfokkinga.github.io/utwente/mmf91m.pdf

I think part of this can be explained by the way recursion is handled on major platforms. Even something like Python which has some functional leanings is prone to stack overflows with deep-ish recursion without hacky workarounds. Once the tools most people are using are more recursion friendly, I think we'll see it become more mainstream. I think JS has TCO now, at least on Node, which is a huge step in that direction.

To understand recursion get "The Little Lisper" or the later book "The Little Schemer". To know when not to use recursion and use iteration instead, look at "Algorithms + Data Structures = Programs" and finally, you can delve into the mathematics of primitive and non-primitive recursive function with "Recursive Functions in Computer Theory".

Good reading to all.

For one it's not handled well by many languages, expensive stack cost, not tail call optimized, max limits on stack, ... It would be nice if you could write recursive algorithms in code and be sure it ran as well and efficient as when you do it manually with for loops and separate stack data structures.

Imperative programmers learn special purpose constructs like loops that only work in simple cases. But since they are so wedded to them, they only reach for the more general tool in more complicated cases. Thus they blame the general tool for the complication.

Just do away with the special cases, and us eg functional calls as the basis for your control flow needs. Then recursion becomes simple.

If necessary, one can introduce loops as a special case later---if working with legacy code or languages that don't properly support function calls. (Eg languages without first class functions and tail call optimizations.)

Recursion is hard, but it is a fundamentally great tool.

If I talk to someone who doesn't understand programming, they can usually understand the if and for statements that you might find in food recipes or in legal contracts.

But almost nowhere outside mathematics and computer science (and certainly not as common as recipes) do you come across recursion.

It's mentally hard to think of a problem so that each step gets simpler.

Solving the towers of hanoi is not straight forward, I can't follow it at the speed that I can read as I could with basic math, I have to really think if what they are suggesting works and how does it work.

However when you get to solving hard problems, recursion really helps. I know from having spent hundreds of hours with interview questions. Bugs can make a problem go from taking me 30 minutes to 4+ hours. Where as using recursion and other functional programming concepts, once I got to the solution it would usually be bug free. So whereas it might not be as fast, I would be more confident in my final answer.

I love the Erlang way of dealing with this:

  % Problem #2

  % Each new term in the Fibonacci sequence is generated by
  % adding the previous two terms. By starting with 1 and 2,
  % the first 10 terms will be:

  % 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

  % By considering the terms in the Fibonacci sequence whose
  % values do not exceed four million, find the sum of the
  % even-valued terms.

  fibsum(_N,M,L) when M >= L -> 0;
  fibsum(N,M,L) when M rem 2 =:= 0 -> M + fibsum(M, N + M, L);
  fibsum(N,M,L) when M rem 2 =:= 1 ->     fibsum(M, N + M, L).

  problem_2(L) -> fibsum(1, 2, L) .

  problem_2_test() -> ?assert(problem_2(100) =:= 44).

  problem_2() -> problem_2(4000000) .

(When familiarizing myself with a new programming language I usually work through several 10's of the project Euler problems, that way I only have to learn one new thing.)

Is recursion difficult? I remember when we did our first recursion in the first year of CS and our professor told us it sould be hard. Then she went on a rant about divide and conquer which made little sense and eventually got to the bit about calling yourself until a criteria.

I think most of us thought it was the easiest part of that year.

Recursion is different. Almost in exactly the same way that geometric proofs are different.

As such, it requires different ways of teaching.

I have used "The Little Schemer" (even back when it was called "The Little Lisper") to teach lots of "non-programmers" (I hate that description) how to do recursion.

I don't think telling people who find a subject difficult that it is easy is very convincing.

Recursion seems fairly straightforward to me if you think about it in terms of how it's typically implemented (the stack and jumps), but that's not quite the mathematical way of thinking about it, I suppose.

I found this HN thread to be quite useful to this conversation: https://news.ycombinator.com/item?id=14949392

Switching to using Erlang full time, closures and functional aspects (returning a function from a function) and recursion was a lot harder for me to grasp than the isolated processes and message passing.

It took a few months to get my head around it, but once you do, it becomes so obviously simple and easy that you start thinking in it directly. All of the sudden having to write "for(i=0;....)" seems eeky and cumbersome when going back to a language which doesn't handle recursion as well (where it will blow the stack for example).

The concept of recursion was easiest to grasp by watching a kid do the maze on a placemat at a restaurant. You go in a line until you find a dead end, then backtrack. Repeat the process until you reach the goal. Each intersection where you make a decision is your function call, and each backtrack is the return result.

I liked this. It reminds me of proof by induction. I recall my teacher telling us it was one of the harder concepts, and thinking, "this sounds just like recursion, and seems pretty natural." I think if she had taken away the scary introductory language, students would have been less afraid of it.

Recursion only begins with the notion of mutual recursion. Transforming imperative loops into recursion (with the constant-space accumulation pattern and TCO) is a nothing-special mechanical operation. Recursion really shines in mutually recursive algorithms, like the famous Hanoi Tower solution.

I think a good analogy to teach recursion are humans, or really any living thing, since they too are functions that call themselves. That is, each time you create a new human, it's function is to create a new human, and so on ad infinitum.

IMHO, the first problem of summing a generalized array of numerical elements is not best solved recursively. I suggest sum(flatten( )) is better and uses less overhead. The subsequent problems under discussion more strongly require recursion.

well I do not think recursion is difficult. but I think doing it in a tail-called optimised way, can sometimes be tricky (especially in compilers or node traversals). that's why more and more cps style recursion comes into place more than often. heck even scala has a way to do cps style tail calls: https://www.scala-lang.org/api/current/scala/util/control/Ta...

Relevant older comment of mine: https://news.ycombinator.com/item?id=11152492

Didn't read the article. I usually don't have trouble with recursion, however lately I have started to avoid it more and more often. It is true that linear solutions usually look more complex. However in my opinion they also allow better reuse of local variables. Their complexity also depends on the datastructure. Designing a linear datastructure for nested problems is sometimes possible and can allow simple non-recursive solutions which I find more elegant.

The Little Schemer is what made me fully comfortable with recursion. It's an amazing teacher.

"There's no such thing as a bad student. Only a bad teacher." - Mr. Miyagi

The easiest way to learn recursion imo is by limiting the domain.

For example, we have a thing called a number:

x

how do we indicate the next number? Well we need a new symbol to distinguish one number from another.

Lets use a marker called prime:

x, x`

Great, now we have two numbers. But let's get a third number. How could we indicate that? Well we could introduce a totally new symbol, like a 'q'.

x, x`, q.

Well that works. but we seem to have just arbitrarily chosen q. There's no immediate obvious aspect of q that lets us know what the next symbol should be if someone asked us to add yet another number. We have three distinct number things but no clear unified way to proceed... But wait, before we took some number x and added a prime to it: x->x` which got us a separate symbol, aka a different number. What if we just do that again but this time with our second number: x`->x`` Great. Now we have three numbers, and we can always use the same rule "add a prime mark" to generate the next symbol, so long as we input the last symbol into our rule:

x, x`, x``

We also wind up with neat little equivalences:

x`` = x`, x = x, x, x

or if our prime operation is a function:

x`` = prime(prime(x)) = prime(x`) = x``

so x``, is just the result of prime of prime of x.

So on and so forth until infinity.

What makes recursion harder to work with in CS is that, unlike summation, you can't go to infinity--you need to terminate the operation eventually if you actually want it to do anything. Because of this and because of the fact that our inputs are not little units like numbers but are usually data structures which require more rules to recurse over, recursion in CS is tightly and innately coupled with pattern matching and the notion of defining bottoms or terminating cases which is not the case for operations in mathematics where we do not care about terminating because it just encodes the rule and isn't actually meant to do anything, and when we do need to do something with it we limit it by deciding when to stop (so I guess some neuron firing is the bottom/terminating case for human operations?).

Recursion in CS is also additionally difficult because we have to worry about how the computer stores the results of each recursive application and feeds them back whereas, kind of like a high level language, our brain just manages all that for us when we do math. Also note that we take huge shortcuts with things like Arabic numerals--which are an incredible advance in efficiency but probably obfuscate the recursive roots of mathematics for most learners (e.g. you just learn that some symbol 2 and some symbol 2 is another symbol 4 and not that these are encapsulating successive applications of the same rule over a set of arbitrary symbols--I mean, your brain knows this deep down--that's why it works, but it makes it difficult to immediately comprehend that it is in fact recursive unless people have pointed this out to you--at least that was my experience; I may have just had bad teachers).

"This article is aimed to introduce and explain a number of topics and ideas that will help you when practicing recursive problems."

I know I'm not supposed to shit talk the article. I know someone spent a lot of time making it for me and others. However, we've gotta move forward as a community. We have to raise the bar. We have to stop this nonsense.

There is an issue here greater than recursion. I know that's bold of me to say, but I'm serious. Programmers need STOP fucking telling people that they can explain something that requires practice to understand. You cannot learn multiplication from reading a blog post. It has to be drilled into you over and over again. And only after it's been drilled into you what numbers are, what addition and subtraction are, and what carrying and borrowing mean. You learn this over the course of YEARS not 5 minutes reading some shitpost on the internet. Recursion is just like math. It has to be drilled into you. I had zero understanding of this for YEARS. And then I picked up a book that drills recursion into you. Only after writing function after function (functions essentially identical to one another in structure), was I able to understand the IMPORTANCE of recursion. Not by thinking about it, or reasoning about it, by actually doing it, over and over again. Recursion can be explained in 10 seconds. I'll do it right now. Recursion is when a set of instructions starts over from step 1. Or for us programmers, a function which calls itself. Bam. all you need to know about recursion. Guess what. It's not enough to understand what multiplication is, you actually have to be able to use it. You actually have to be able to use recursion. Explaining why multiplication is important is frankly retarded. This post is frankly retarded. STOP pretending that you can explain in 5 minutes what took you months and years to understand. STOP. All you do is make people like me think they're dumb for not getting it. I'M SMARTER THAN YOU! But it took me months of ACTUALLY WRITING RECURSIVE FUNCTIONS to realize HOW FUCKING DUMB YOU ALL ARE. Stop fucking telling people you can teach them calculus in 5 minutes. Stop telling them that all it takes is this one clear explanation. It doesn't! It takes actual work. Fuck the guy who wrote that post. You have no idea how many years I wasted thinking blog posts like this were how to learn. If you don't get why recursion is a big deal, do yourself a favor and forget everything you read in that post, grab a pencil, some paper, and a copy of the Little Lisper. Email me in 6 months when you're finished, so that you can thank me for being the only one to tell you the truth about recursion.

Recursion isn't difficult. I never had a problem understanding it. Stepping through a recursive function with a debugger that shows you the current stack trace should make it plain as day how it works.

Not trying to toot my own horn or try to make an appearance on /r/iamverysmart, but where are people struggling when it comes to understanding recursion?