>It’s also astonishing to me that people in a position to explain even moderately complex computing ideas continue to treat recursion as somehow 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.
Clearly when we communicate with others using regular language we use a repeat keyword rather then recursive grammar. No natural language on the face of the earth ever communicates the concept of repetition via recursion* There's always some keyword or number for repeating something.
*(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.
Fair point. My point is that looping should be immediately obvious to a beginner due to a 1 to 1 mapping with human communication. Thus recursion when compared to iteration is way harder.
I don't think anyone's opposed to having a function for "repeat this thing 5 times". But if you did see a function that called itself, why would that be any more confusing than seeing a function that calls another function? That's all it is.
I think it's because for beginners it's hard to see why it would be useful (or not just turn into infinite regression). Proof by induction is often similarly difficult for maths students to grasp. The idea of solving a problem by breaking it down into smaller problems until each part of it becomes trivial is not something which comes naturally to most people, it's a learned and ingrained habit in those who have been taught it and used it.
> I think it's because for beginners it's hard to see why it would be useful (or not just turn into infinite regression).
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.
Only in hindsight. In reality looping is much more easily grasped due to the one to one mapping with human language. Looping should be taught on day 1, not recursion.
In hindsight lots of unfamiliar concepts are easy. Teaching programming with imperative constructs first encourages imperative thinking. Teaching programming with computational concepts encourages computational thinking. Both require some reasoning about syntax and control flow before they sink in enough for beginners to use them effectively. But I really don’t think human language has any bearing here. People are also very likely to already understand expressions, as they’re taught from a very early age in arithmetic and it’s very common for people to at least have some algebra education. Expressions are fundamentally easier to reason about, and there’s no reason they would be more difficult to a beginner.
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.
>Teaching programming with imperative constructs first encourages imperative thinking. Teaching programming with computational concepts encourages computational thinking
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.
> Imperative thinking is computational. All forms of thinking are computational by definition.
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))))))
And that’s precisely how I was taught multiplication. It was just written with infix:
5 * 6 = 5 + 5 + 5 + 5 + 5 + 5
Which, the teacher demonstrated can be partially unwrapped:
5 * 6 = 5 + 5 * 5
And so on. All you have to do to teach that as recursion is declare those operators as functions and call them. You can also use this to teach reduce, which is just a generalized recursive loop expression.
> 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.
In math iteration and recursion are defined as sibling isomorphic concepts. You can desugar recursion into iteration and you can “desugar” iteration into recursion. See Turing completeness and lambda calculus. The topic at hand is which angle provides a better view of this singular isomorphic concept (iteration vs. recursion) that makes it easier to understand. The isomorphism itself (which is what your expose gets into) is already well known.
You're not comparing like with like - you're comparing a repeat function (or keyword) with the implementation of a repeat function. The imperative equivalent would be something like "make an int called i, then repeatedly add one to i, checking whether i is less than five, and each time you do that do the special task", which is by no means clearer. And if anything writing a "repeat" function is easier in the functional world than the imperative one, since traditional imperative languages don't have first-class functions.
This is because you don't understand humans. Which is more clear to you?
Clearly when we communicate with others using regular language we use a repeat keyword rather then recursive grammar. No natural language on the face of the earth ever communicates the concept of repetition via recursion* There's always some keyword or number for repeating something.*(not 100% sure on this, HNers, prove me wrong if possible, I'm open to being wrong).