5 ms·

>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

>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).

lmm 6y ago
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.
- rcxdude 6y ago
  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.
  - eyelidlessness 6y ago
    > 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.
    - Geminidog 6y ago
      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.
      - eyelidlessness 6y ago
        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.
        Geminidog 6y ago
        >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.
- Geminidog 6y ago
  Look at my example. if you literally communicated with someone that way would the other person be confused? The answer is yes.
  - lmm 6y ago
    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.
eyelidlessness 6y ago
> This is because you don't understand humans. 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.
- Geminidog 6y ago
  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.

lmm 6y ago

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.

rcxdude 6y ago
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.
- eyelidlessness 6y ago
  > 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.
  - Geminidog 6y ago
    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.
    - eyelidlessness 6y ago
      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.
      - Geminidog 6y ago
        >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.
Geminidog 6y ago
Look at my example. if you literally communicated with someone that way would the other person be confused? The answer is yes.
- lmm 6y ago
  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.

eyelidlessness 6y ago

> This is because you don't understand humans. 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.

Geminidog 6y ago
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.