5 ms·

For loops don't require keeping track of multiple levels of state; you just need a counter. It's very easy to walk through a for-loop on pen and paper. Walking

For loops don't require keeping track of multiple levels of state; you just need a counter. It's very easy to walk through a for-loop on pen and paper. Walking through recursion is much trickier since you have to keep track of your stack.

feoren 2y ago
But you don't need to "walk through" recursion, you just need to assume the sub-calls do the correct thing. That's the magic of it -- like induction in proofs, if you convince yourself that the function does the correct thing if all of its self-calls do the correct thing, then your function is totally correct.
- QuercusMax 2y ago
  Induction is really not that intuitive. Saying "just trust the magic" doesn't help a noob get it.
  - kelipso 2y ago
    Induction is basically the first thing you learn in your freshman intro to proofs class. Probably US high school geometry classes teach it too, I don't remember, but it can be easily taught to sophomore high school students. So you saying it's not intuitive is a bias that came from your previous experience, not from reality. Induction is literally the simplest type of proof you do in math, and of course there's a 1-1 relationship between induction and recursion. Induction is also the basic way that you discover/invent an algorithm in CS, which is usually taught in junior level CS algorithms classes in all the top colleges. So I think it's just a problem with people just not learning a fairly simple concept or just skipping intro to algo classes altogether.
    - QuercusMax 2y ago
      Induction and proofs are taught REALLY REALLY badly in most US high schools and many colleges. It's not intuitive, even though it may be simple.
      - kelipso 2y ago
        Since it's simple, the question of whether it is intuitive or not depends on how well you learn it. It's such a core part of algorithm design that you should make it intuitive to yourself in order to be a better programmer.
  - agalunar 2y ago
    It's a familiar concept to most people, though: most people understand that people have parents, grandparents, greatgrandparents, and so on. (Maybe a bad example; I feel like it shows that people are familiar with coinduction.)
  - chrismcb 2y ago
    Induction should be intuitive. I think there are a few things that get lost. One is you need to show the steps are equivalent. You have to show going from n-1 to n is similar to going from n to n+1. My favorite analogy is coming stairs. You prove you can get from the floor to the first step (that is the base case) but you also have to show that all the stairs are identical. I think this is where a lot of people misunderstand induction.
- nick7376182 2y ago
  Nice in theory, but then debugging non-trivial recursive functions would not be my idea of a good time.

feoren 2y ago

But you don't need to "walk through" recursion, you just need to assume the sub-calls do the correct thing. That's the magic of it -- like induction in proofs, if you convince yourself that the function does the correct thing if all of its self-calls do the correct thing, then your function is totally correct.

QuercusMax 2y ago
Induction is really not that intuitive. Saying "just trust the magic" doesn't help a noob get it.
- kelipso 2y ago
  Induction is basically the first thing you learn in your freshman intro to proofs class. Probably US high school geometry classes teach it too, I don't remember, but it can be easily taught to sophomore high school students. So you saying it's not intuitive is a bias that came from your previous experience, not from reality. Induction is literally the simplest type of proof you do in math, and of course there's a 1-1 relationship between induction and recursion. Induction is also the basic way that you discover/invent an algorithm in CS, which is usually taught in junior level CS algorithms classes in all the top colleges. So I think it's just a problem with people just not learning a fairly simple concept or just skipping intro to algo classes altogether.
  - QuercusMax 2y ago
    Induction and proofs are taught REALLY REALLY badly in most US high schools and many colleges. It's not intuitive, even though it may be simple.
    - kelipso 2y ago
      Since it's simple, the question of whether it is intuitive or not depends on how well you learn it. It's such a core part of algorithm design that you should make it intuitive to yourself in order to be a better programmer.
- agalunar 2y ago
  It's a familiar concept to most people, though: most people understand that people have parents, grandparents, greatgrandparents, and so on. (Maybe a bad example; I feel like it shows that people are familiar with coinduction.)
- chrismcb 2y ago
  Induction should be intuitive. I think there are a few things that get lost. One is you need to show the steps are equivalent. You have to show going from n-1 to n is similar to going from n to n+1. My favorite analogy is coming stairs. You prove you can get from the floor to the first step (that is the base case) but you also have to show that all the stairs are identical. I think this is where a lot of people misunderstand induction.
nick7376182 2y ago
Nice in theory, but then debugging non-trivial recursive functions would not be my idea of a good time.