When TCO recursion was first developed it was very explicitly called out as a syntactic and structurally improved GOTO but still fundamentally a GOTO that could take params.

Recursion isn't physically real, any book that teaches the abstraction before explaining either the call stack (for non-TCO recursion) or in the GOTO context is a book actively trying to gatekeeper CS and weed out readers. (Not that any of those old pascal turbo/boreland books from the 90s actually shipped code that compiled.)

I had several people on HN of all places try to "teach me" recursion after this simple line inside a larger comment:

> It's like acting like recursion is physically real (it's not) when it smuggles in the call stack.

Recursion IS real abstractly. It's just not physically real, it was developed before we knew how DNA/RNA encoding handles the same issues in a more performant way.

▲

SJC_Hacker 5 days ago | parent | next [-]

I don't see how it would be gatekeeping.

Recursive functions are a mathematical concept, like the "imaginary" number, or "trascendental" numbers. Or negative numbers for that matter.

Simple example, the Fibonacci sequence. FIB(1) = 1 FIB(2) = 1 FIB(N) = FIB(N-1) + FIB(N-2)

There's no programming language or "physical" implementation needed in order to calculate FIB(N) for arbitrary N. Pencil and paper will do for small numbers

▲

fellowniusmonk 4 days ago | parent [-]

Yes, you cannot hide the callstack when taught with pencil and paper.

But in computer programing it is often hidden.

And then you are misleading people about recursion and not helping them to build mental models that map to the physical/hardware process.

This isn't a big deal or anything, it's hardly worth talking about but it is literally a true thing many don't realize and that does empirically negatively effect education of the concept.

▲

SJC_Hacker 4 days ago | parent [-]

> Yes, you cannot hide the callstack when taught with pencil and paper.

Recursive functions were mathematically defined well before the callstack or the von Neumann architecture was a thing. Godel, Church and Kleene did alot of work on them in the 1930s (and I believe even prior to that infinite series were defined recursively although functional theory had not be worked out), this was before ENIAC (1945) which would be just barely recognizable as a general purpose computer and didn't have anything like CALL instruction.

So I don't understand this notion of "hiding the callstack" comes from. If one cannot understand recursion without invoking the callstack, well thats just them. But I don't see how its absolutely necessary or some universal

	▲	fellowniusmonk 4 days ago \| parent [-]
		I have no complaints about how recursion is taught in mathematics courses. I'm being quite clear that I take issue with how the concept has been taught in many programming books and courses. You can see the ignorance and confusion in this very thread.

▲

Jtsummers 5 days ago | parent | prev | next [-]

> Recursion isn't physically real, any book that teaches the abstraction before explaining either the call stack (for non-TCO recursion) or in the GOTO context

Do you also believe that loops and functions should only be taught after the call stack and goto are taught? Neither of them are real either by your measure.

What a silly sentiment.

	▲	fellowniusmonk 5 days ago \| parent [-]
		Loops and functions can be physically represented as a stand alone, they can be physically carved onto a mechanical surface and observed. They don't smuggle anything in conceptually, their abstraction doesn't leave anything critical to their structure out. They are real and can be physicalized as stand alone objects. I see you've never tried to teach a software class to children or other learners, historically recursion is _very_ poorly taught by those who already understand the concept, but I'm not saying you have to care about that, a lot of people think there are too many programers already.

▲

achierius 5 days ago | parent | prev | next [-]

> It's just not physically real, it was developed before we knew how DNA/RNA encoding handles the same issues in a more performant way.

That was a sharp left turn -- how do you figure DNA/RNA are relevant here? I feel like iteration pre-dates our modern understanding of RNA in particular (though I could be mistaken) so I struggle to imagine how DNA/RNA were particularly informative in this regard.

▲

ndriscoll 4 days ago | parent | prev [-]

For basic structural recursion on finite data structures, all you're doing is case analysis and substitution (i.e. "plugging in" values). How is that gatekeeping?

Math majors cover hundreds of algorithms per semester often using recursion without thinking much of it. For that matter, same with "higher order functions" (e.g. derivative operators, or even just translation/scaling of a graph). Even in introductory calculus, students cover things like fixed points (e.g. I remember discussing d^4/(dx)^4 sin = sin almost immediately after introducing derivatives).

Thinking in terms of physical machines is useful for reasoning about performance, but seems like a distraction for learning to think logically/correctly, which seems like a more important first step?