7 ms·

Firstly, there's a nuance here that readability is heavily dependent upon the language. A language where recursion is the recommended approach to these sorts of

by samhh 7y ago

Firstly, there's a nuance here that readability is heavily dependent upon the language. A language where recursion is the recommended approach to these sorts of problems will have far better syntax for doing so, such as in Haskell. Secondly, I think there's something to be said for familiarity. I think looping is second nature to most of us not because it's superior or more intuitive, but because traditionally this is one of the first things we're all taught. If functional programming were the norm and people were taught recursion early on instead I think your notion of simplicity would differ. I've been teaching a little bit of programming to a beginner lately, and they've often found functional approaches to problems easier to grasp than their imperative equivalents because they're more mathematical. It's like an expression of something they already know versus looping, mutability, et al which are new concepts entirely.

Scarbutt 7y ago
As someone who learnt to program in Scheme, this was true for me, did so much Scheme that when doing some C or JS I had to pause for moment and think harder when writing imperative loops.
seanmcdirmid 7y ago
Looping has a huge advantage in terms of how we do things in real life. We don’t think of “pound 100 fence posts into the ground” recursively. Recursion is much more of a mathematical concept that we learn about long after preschool, while my 3 year old already gets loops.
- jacksnipe 7y ago
  Honestly I'm going to disagree. Yes, when planning the task, I think about it as "I have to do this 100 times". But when I'm actually performing the task, I think "Ok, I have to get this stake in the ground, then proceed w/ the rest of my giant pile of stakes." On the flipside, I have a lot of mathematical training, so maybe this is an uncommon perspective.
  - deleted 7y ago
    [deleted]
- loup-vaillant 7y ago
  > Looping has a huge advantage in terms of how we do things in real life. Anthropomorphism is the bane of our craft. Our untrained intuitions don't really matter. > Recursion is much more of a mathematical concept that we learn about long after preschool Programming is applied mathematics. Different from the kind of maths you learn at school of course, and often even more rigorous. I personally have no qualms about requiring some mathematical proficiency in programming. Makes you much more capable at a number of applications later on.
  - jmilloy 7y ago
    > Our untrained intuitions don't really matter. On the contrary, we have no choice but to use our intutions, at whatever level of training they are at, all the time. So it matters a lot. If A is easier than B iff we learn to think differently, but learning to think differently is harder than just doing B, then A isn't actually easier than B.
    - loup-vaillant 7y ago
      Becoming seriously proficient at anything seriously alters the way you think about it, no matter the field. For instance, I play the Cello. Lately, I noticed I only made progress when I understood something, or changed a habit, or let go of some subtle, but ultimately far reaching assumption. I played the Witness. There's a time based challenge at some point, that I could only beat when I changed the way I thought about those puzzle just so I could go through them faster. I learned to touch type. To do that, I stopped thinking visually, and instead think kinaesthetically. Then I developed some kind of intuition, where I think a word, and the letters just flow through my fingers. I don't really think at the letter level any more. Neither does anyone proficient with a keyboard. (50 WPM and up). Our untrained intuitions don't really matter. Seriously learning anything trains us out of them. Programming is no different.
  - seanmcdirmid 7y ago
    Plenty of people learn how to program without learning the requisite math first. I wrote my first program when I was 8 years old, long before I learned even algebra. I think it is still the case that most people learn how to program before they even know what the word recursion means.
- rapind 7y ago
  I'm not so sure. Seems to me that often you want to pound fence posts into the ground 3 feet apart until you enclose the desired area.
- carapace 7y ago
  Hmm, aren't all living things recursive? (BTW, big fan of your work!)
- svat 7y ago
  Donald Knuth has the opposite view: he thinks recursion is more fundamental. Funnily, he uses an example much like yours. > On the other hand, recursion is quite fundamental. It is not inherently a high-level concept, suitable only for grownups but not for children. Most people actually grew up with an implicit understanding of rudimentary recursion long before they understood iteration—that is, before they understood how to carry out a loop of instructions. Given a list of tasks to do, the simplest mode of operation is a recursive approach that charges blindly ahead: […] > It's only after we've gained experience with such an almost mindless method that we acquire a more global view of the process: > Do Jobs = Do each job on the list. (2) > […] > Do a_k for 1 ≤ k ≤ n. (5) > All computer programmers have in fact progressed from stage (1) to these later stages rather early in our lives, because of an inner desire to “see through” the entire chain of consequences that result from primitive actions. > Furthermore, once we reached these later stages, we entirely forgot that they were actually elaborations of the recursive procedure in (1). There was no point in narrowing our perspective to the simple-minded form. The vast majority of recursive situations that faced us as children fell into very simple patterns that could readily be “seen through” and understood as a unit. Thus we came to understand iteration as an elementary idea. > It was only later, when faced with difficult problems whose recursive structure cannot be visualized in straightforward terms such as operations on arrays of elements, that we re-learned the importance of recursion. Therefore we now tend to regard recursion as a high-level concept, although it is really fundamental. Possibly these views of his are influenced by his early background in programming in assembly/machine language, where it takes some sophistication to translate recursive ideas into code (maintaining a stack etc), but it's an interesting point of view worth some consideration. This is from his draft of TAOCP Chapter 8 ("Recursion"), and is preceded by the following paragraph: > High-level languages for computing—which themselves are de ned recursively, because algebraic formulas are built up from algebraic formulas—allow programmers to pretend that recursion is real, that a computer is somehow manufactured from recursive components. But programs that invoke themselves are actually implemented by means of a stack structure behind the scenes. A good programmer is able to understand such algorithms by viewing them simultaneously at a high level and at the machine level, and at many levels in between, thereby perceiving what a real computer can actually do well.
- deleted 7y ago
  [deleted]
- jbjohns 6y ago
  From a perspective of what we do in real life, I think looping and recursion are the same thing. Pound 100 fence posts into the ground is either "do this, then loop back and do it again until some stop point" (iterative) or "the base case is no posts left where you stop, otherwise pound the current posts into the ground" recursive. Recursive has the advantage that when you use the tools for it, recursive is easier to read. If I see e.g. a map, I know we're converting a collection of things to some other things without restriction. With a look, I just have to read through it to see what it's doing.
andrewprock 7y ago
Recursion tends to strip context. That is one of the features, and one of the drawbacks. All problems are either a base case, or the general case. If you are attempting to debug logic, it often helps to have all the context. To do that in recursion, you have to travel up and down the stack, examining local contexts one by one.
- jbjohns 6y ago
  I'm not sure what you mean here. The only thing I can come up with is you're talking about writing specific code recursively but when doing functional programming we usually just use the applicable recursive function (e.g. map, filter, reduce) in which case we have better context than with a loop because a loop has a lot of irrelevant implementation details cluttering up the context.
baddox 7y ago
It's also probably the case that readability is not a primary concern when implementing things like "min" that will most likely be in the standard library of a programming language. From my limited experience looking at such source code, there tend to be a surprisingly large about of code for fixing edge cases, esoteric performance problems, etc. It may be instructive to look at how readable a very naive implementation of a basic function like "min" is, but it probably doesn't actually matter that much in practice, because you'll be using what the standard library offers (and its implementation is probably much less straightforward than you might think).

by samhh 7y ago

Scarbutt 7y ago

As someone who learnt to program in Scheme, this was true for me, did so much Scheme that when doing some C or JS I had to pause for moment and think harder when writing imperative loops.

seanmcdirmid 7y ago

Looping has a huge advantage in terms of how we do things in real life. We don’t think of “pound 100 fence posts into the ground” recursively. Recursion is much more of a mathematical concept that we learn about long after preschool, while my 3 year old already gets loops.

jacksnipe 7y ago
Honestly I'm going to disagree. Yes, when planning the task, I think about it as "I have to do this 100 times". But when I'm actually performing the task, I think "Ok, I have to get this stake in the ground, then proceed w/ the rest of my giant pile of stakes." On the flipside, I have a lot of mathematical training, so maybe this is an uncommon perspective.
- deleted 7y ago
  [deleted]
loup-vaillant 7y ago
> Looping has a huge advantage in terms of how we do things in real life. Anthropomorphism is the bane of our craft. Our untrained intuitions don't really matter. > Recursion is much more of a mathematical concept that we learn about long after preschool Programming is applied mathematics. Different from the kind of maths you learn at school of course, and often even more rigorous. I personally have no qualms about requiring some mathematical proficiency in programming. Makes you much more capable at a number of applications later on.
- jmilloy 7y ago
  > Our untrained intuitions don't really matter. On the contrary, we have no choice but to use our intutions, at whatever level of training they are at, all the time. So it matters a lot. If A is easier than B iff we learn to think differently, but learning to think differently is harder than just doing B, then A isn't actually easier than B.
  - loup-vaillant 7y ago
    Becoming seriously proficient at anything seriously alters the way you think about it, no matter the field. For instance, I play the Cello. Lately, I noticed I only made progress when I understood something, or changed a habit, or let go of some subtle, but ultimately far reaching assumption. I played the Witness. There's a time based challenge at some point, that I could only beat when I changed the way I thought about those puzzle just so I could go through them faster. I learned to touch type. To do that, I stopped thinking visually, and instead think kinaesthetically. Then I developed some kind of intuition, where I think a word, and the letters just flow through my fingers. I don't really think at the letter level any more. Neither does anyone proficient with a keyboard. (50 WPM and up). Our untrained intuitions don't really matter. Seriously learning anything trains us out of them. Programming is no different.
- seanmcdirmid 7y ago
  Plenty of people learn how to program without learning the requisite math first. I wrote my first program when I was 8 years old, long before I learned even algebra. I think it is still the case that most people learn how to program before they even know what the word recursion means.
rapind 7y ago
I'm not so sure. Seems to me that often you want to pound fence posts into the ground 3 feet apart until you enclose the desired area.
carapace 7y ago
Hmm, aren't all living things recursive? (BTW, big fan of your work!)
svat 7y ago
Donald Knuth has the opposite view: he thinks recursion is more fundamental. Funnily, he uses an example much like yours. > On the other hand, recursion is quite fundamental. It is not inherently a high-level concept, suitable only for grownups but not for children. Most people actually grew up with an implicit understanding of rudimentary recursion long before they understood iteration—that is, before they understood how to carry out a loop of instructions. Given a list of tasks to do, the simplest mode of operation is a recursive approach that charges blindly ahead: […] > It's only after we've gained experience with such an almost mindless method that we acquire a more global view of the process: > Do Jobs = Do each job on the list. (2) > […] > Do a_k for 1 ≤ k ≤ n. (5) > All computer programmers have in fact progressed from stage (1) to these later stages rather early in our lives, because of an inner desire to “see through” the entire chain of consequences that result from primitive actions. > Furthermore, once we reached these later stages, we entirely forgot that they were actually elaborations of the recursive procedure in (1). There was no point in narrowing our perspective to the simple-minded form. The vast majority of recursive situations that faced us as children fell into very simple patterns that could readily be “seen through” and understood as a unit. Thus we came to understand iteration as an elementary idea. > It was only later, when faced with difficult problems whose recursive structure cannot be visualized in straightforward terms such as operations on arrays of elements, that we re-learned the importance of recursion. Therefore we now tend to regard recursion as a high-level concept, although it is really fundamental. Possibly these views of his are influenced by his early background in programming in assembly/machine language, where it takes some sophistication to translate recursive ideas into code (maintaining a stack etc), but it's an interesting point of view worth some consideration. This is from his draft of TAOCP Chapter 8 ("Recursion"), and is preceded by the following paragraph: > High-level languages for computing—which themselves are de ned recursively, because algebraic formulas are built up from algebraic formulas—allow programmers to pretend that recursion is real, that a computer is somehow manufactured from recursive components. But programs that invoke themselves are actually implemented by means of a stack structure behind the scenes. A good programmer is able to understand such algorithms by viewing them simultaneously at a high level and at the machine level, and at many levels in between, thereby perceiving what a real computer can actually do well.
deleted 7y ago
[deleted]
jbjohns 6y ago
From a perspective of what we do in real life, I think looping and recursion are the same thing. Pound 100 fence posts into the ground is either "do this, then loop back and do it again until some stop point" (iterative) or "the base case is no posts left where you stop, otherwise pound the current posts into the ground" recursive. Recursive has the advantage that when you use the tools for it, recursive is easier to read. If I see e.g. a map, I know we're converting a collection of things to some other things without restriction. With a look, I just have to read through it to see what it's doing.

andrewprock 7y ago

Recursion tends to strip context. That is one of the features, and one of the drawbacks. All problems are either a base case, or the general case. If you are attempting to debug logic, it often helps to have all the context. To do that in recursion, you have to travel up and down the stack, examining local contexts one by one.

jbjohns 6y ago
I'm not sure what you mean here. The only thing I can come up with is you're talking about writing specific code recursively but when doing functional programming we usually just use the applicable recursive function (e.g. map, filter, reduce) in which case we have better context than with a loop because a loop has a lot of irrelevant implementation details cluttering up the context.

baddox 7y ago

It's also probably the case that readability is not a primary concern when implementing things like "min" that will most likely be in the standard library of a programming language. From my limited experience looking at such source code, there tend to be a surprisingly large about of code for fixing edge cases, esoteric performance problems, etc. It may be instructive to look at how readable a very naive implementation of a basic function like "min" is, but it probably doesn't actually matter that much in practice, because you'll be using what the standard library offers (and its implementation is probably much less straightforward than you might think).