Calling a function can be easily, and incorrectly, modeled by representing the arguments as variables stored at a fixed position in memory. (As function calls used to work.) Once you introduce recursion, this model breaks down and you are forced to think in terms of activation records/stackframes.

Probably those people learnt function calls in the former way first, meaning that recursion represented a conceptual leap for them.

First, realizing that you can have separate instances of functions at the same time -- different stack frames. Making the mental leap from "the content of x in function f" to "the content of x in f(0), and also the content of x in f(1)" is a leap of abstraction, but not necessarily a tremendous one.

Second, mentally modeling recursion when it gets complicated. Simple recursive cases are easy to model in your head, because either there is little state to keep track of, or because you can extrapolate the pattern between function calls, mentally compressing the state of the whole call tree.

Tail-call optimization, for example, is really easy to mentally model because you only have to keep track of the state of one function's variables at a time -- unless you start passing continuations or thunks into your function calls, in which case you're carrying a stack of unlimited complexity into each function call. It's still just a function call, with the same number and types of arguments, but now one or more of those arguments contains turing-complete, recursive programs of unlimited complexity.

This similar to the worst-case mentally-complicated recursion without TCO, where you can build a complex graph of function calls, scopes, shared data accesses, and mutated copies of what used to be the same data, that can all be present at once, and where you might need to keep track of all of them in order to track down and understand something that you need to understand.

You can, of course, build similarly tangled-up structures in a purely-iterative manner, but the upside is that the complexity will be confined to the data state -- there will be no call tree to mentally model, and no need to track variable scope.

---

Shorter version: if the efficiency and elegance of recursion (with appropriate compiler/runtime optimizations, like TCO) is like zip compression for your mental model of code complexity, then there exist recursive-program equivalents of zip bombs.

---

Even shorter version: recursion itself isn't hard to reason about, but recursive programs can be very hard to reason about

This is because you don't understand humans. Which is more clear to you?

    repeat special-task 5 times. 

    (do special-task n times) = (do special-task n - 1 times)
    (do special-task 0 times) = Don't do anything. 
    do special-task 5 times.

*(not 100% sure on this, HNers, prove me wrong if possible, I'm open to being wrong).

I don’t think it’s about so large and broad a group, or about human language. No one speaks in dynamic property access or dependency inversion or binary compilation or a zillion other concepts in programming that aren’t misrepresented as “hard to understand”.

My point isn’t that it’s something that would be immediately obvious to a beginner, but that its difficulty is often overstated when introduced.

And that, in turn, I think is because most beginners are first introduced to mutation and statements and all kinds of “do” stuff instead of trivial algebra with trivial types.

If the core primitives at the start are:

1. Computation producing output

2. Computation of input producing output

3. Wrapping #2 in a function

I could see introducing recursion in an easily understandable way on day one.

I’d even say that people usually have a good grasp on recursion even if they don’t know that’s what it’s called. Multiplication is just recursive addition. Exponents are just recursive multiplication. And so on.

Imperative thinking is computational. All forms of thinking are computational by definition.

> Expressions are fundamentally easier to reason about, and there’s no reason they would be more difficult to a beginner.

What does expressions have to do with anything. Recursion can be both defined in an expression and as an imperative jump instruction. The concept is orthogonal to expressions.

>I’d even say that people usually have a good grasp on recursion even if they don’t know that’s what it’s called. Multiplication is just recursive addition. Exponents are just recursive multiplication. And so on.

But people don't think of multiplication this way. The teacher doesn't teach multiplication to you in terms of recursion she literally teaches you it with the "times" keyword. What's 5 * 6? Add 5 to 5, 6 times.

It has bearing on language. Nobody outside of programming/mathematics communicates concepts recursively. Our communication is a reflection of how we think naturally. Recursion takes training. Looping is just learning syntax for a concept we already know about: repetition.

I meant in the mathematical sense. Math doesn’t have imperative statements and side effects.

> What does expressions have to do with anything. Recursion can be both defined in an expression and as an imperative jump instruction. The concept is orthogonal to expressions.

In case it wasn’t clear, I’ve been arguing this whole time for teaching pure FP concepts. Starting with computing a value, then computing a value from input, then with a function returning a value computed from its input... then with a function computing a value recursively from its input. Recursion is the fundamental building block for repetition in FP. Even if you can express it with a loop-like expression it eventually desugars to recursion.

> But people don't think of multiplication this way. The teacher doesn't teach multiplication to you in terms of recursion she literally teaches you it with the "times" keyword. What's 5 * 6? Add 5 to 5, 6 times.

That... is recursion. It’s mind boggling to me that it’s not plain as day, here in this context. It’s literally:

    (+ 5 (+ 5 (+ 5 (+ 5 (+ 5 5))))))

    5 * 6 = 5 + 5 + 5 + 5 + 5 + 5

    5 * 6 = 5 + 5 * 5

> It has bearing on language. Nobody outside of programming/mathematics communicates concepts recursively. Our communication is a reflection of how we think naturally. Recursion takes training. Looping is just learning syntax for a concept we already know about: repetition.

From a learning perspective, they’re literally just different syntax for the same thing. Recursion is just moving the repetition intent to the body of the loop and eliminating intermediary values. There’s no reason other than tautology that one syntax is easier to learn than the other.

I remember javascriptcore solving this issue by using a "shadow stack"

I was experimenting with a simple indirect-threaded interpreter, which I wanted to write in a "nice" style (1 function per opcode) but have compiled in an "optimized" way (state machine). Playing around in Godbolt, I found out that the compilers managed to detect & optimize even indirect tail calls, i.e. tail calls to function pointers. This was indeed on a toy example (i.e. like 5 functions, not a real interpreter with 100 different opcodes) but still truly amazing.

The reason for this was, I was trying to replicate LuaJIT2 - Mike Pall was complaining that the reason interpreters written in C are slow is, that the compiler cannot optimize & register-allocate a large function containing a switch statement for 100 opcodes. Instead, he wrote the interpreter in asm, and made sure all important variables are kept in registers. My thesis was that we could do the same thing by having a bunch of functions tail-calling each other, with all important variables as parameters (which would be optimized into registers). Better, actually, because the compiler could improve register allocation within each "opcode"/function.

Or you can use the rr-debugger, and just return back to the exact sequence of calls, and reject the need to pick between optimization and debugging :D

https://stackoverflow.com/questions/65225761/trying-to-delib...