Hacker News Reader

Comment by kelipso | Hacker News Reader

Coming from a math background and going into algorithms class, recursion was much easier to grasp than for loops. It really is a pedagogy thing.

I think it comes from the fact that lot of CS majors go into college with years of experience with for loops and barely knowing what recursion is. If you start from a blank slate, I am confident recursion is much easier to understand.

View on HN

Math background here too. Long before I first sat down at a computer (in 1981), we learned about the inductive principle in math class, and did some proofs with it. Later on, our introduction to recursion (in Pascal) started with a review of induction.

Of course the next phase is trying to do everything with recursion.

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.

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.

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.

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.

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

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

I am confident, from remembering the troubles other students had when recursion was introduced, that recursion is indeed very difficult for some students.

I'm not even sure that iteration was easy for them.

Just because it is easy for one person does not make it easy for another. There are some people who love high school geometry and hate high School trigonometry, and vice versa, because the former deals with proofs for the most part and the latter deals with application (at least when I was taught it).

Probably because it's taught badly. From one of the other responses:

> you just need to assume the sub-calls do the correct thing.

This is technically correct (and I remember hearing it when first learning recursion), but it's not useful. The two most common problems were not having a good stopping condition, and handling two or more levels per call because they didn't understand at what point the function should call itself.

I think the first thing that needs to happen is just draw a diagram of common data structures and show how they can be looked at as a recursive data structure. Like a tree is a node and two more trees, or a list is a node and another list. As odd as it may sound to some people, I think starting with something that has a visual representation like that (even if it's more complicated in code) is easier to understand than pure math like recursive fibonacci.

This would also double as an answer to the "why would I use this when I can just use a loop?" question. Just challenge the student to walk a tree with loops instead of recursion to see how much more work it is.

Reply on news.ycombinator.com