Hacker News Reader

Comment by feoren | Hacker News Reader

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.

View on HN

Induction is really not that intuitive. Saying "just trust the magic" doesn't help a noob get it.

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.

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.

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.

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

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.

Nice in theory, but then debugging non-trivial recursive functions would not be my idea of a good time.

Reply on news.ycombinator.com