Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Stop Telling Students Recursion is Hard

jinfiesto.posterous.com

Post reply on HN
Print view View original

61–70 of 111 posts

Re: Stop Telling Students Recursion is Hard

#61

Post by sirclueless »

pg wrote: post #26

When I was writing Ansi Common Lisp I spent a while thinking about why students find recursion a difficult concept. I decided it was because they think of a function as a machine for doing something. E.g. the length function as a machine that finds the lengths of lists. If you think of a function instead as a definition-- e.g. as the definition of length-- then suddenly it's not difficult anymore. At least, that was…

The problem with doing away with the implementation specific details of recursion is that these details are inextricably linked to the correctness of your program in most languages.

The fact is, even with modern optimizing compilers that prove all sorts of correctness theorems about transformations, stack overflows will occur in recursive programs if you aren't constantly aware of their existence. You always have to code recursive programs defensively.

A program coded like "recurse(n-1)" will probably blow its lid if you pass in 1,000,000 as the parameter while "for (i=0; iExplaining why these differences are important to a beginning student, let alone teaching them how to avoid them on their own, is a task that can only get in the way. Avoiding recursion for a while is a much better way to make first few attempts at independent coding not go up in flames.

Re: Stop Telling Students Recursion is Hard

#62

Post by Sherlock »

oniTony wrote: post #16

Interestingly enough, in curriculums that start out with functional languages (e.g. Scheme) students have little trouble with recursion... and then consider iterative loops to be "hard".

Wow, that's surprising, I'd love to hear about some (anecdotal) evidence supporting this.

Re: Stop Telling Students Recursion is Hard

#63

Post by brlewis »

dkarl wrote: post #30

Recursion is a natural idea. When humans perform repetitive tasks, we don't assign state variables, and we generally don't keep counters. We just keep doing the same thing over and over until we arrive at some kind of terminating condition. That's a while loop. To eat a bowl of Cheerios, keep spooning Cheerios into your mouth while there are more Cheerios in the bowl. Telling students that recursion is hard isn't a g…

I've been hearing experienced programmers opine for a long time that while is the more natural representation of repetitive tasks. Twelve years ago my oldest was learning to walk upstairs. I watched her say "up", go up one stair, then say "up" again, and go up the next stair. This concrete example of recursively calling the "up" function did more to convince me that recursion is natural than any explanation with abstract words like "keep doing the same thing".

>As soon as they figure out that for and while loops are sufficient to express all the programming ideas they can come up with, they won't want to learn anything else.

This is contrary to my firsthand experience. As a teenager, I did BASIC programming. I had a magazine (printed on paper; I'm dating myself) with a BASIC program listing that generated mazes. I could not wrap my head around what that program was doing. At some point my parents bought me FORTH, which does have recursion. That was sufficiently expressive for me to understand how to generate a maze, and even write the program myself without an example. Yes, it's possible to express any programming idea with loops, but many ideas are much more easily expressed with recursion.

Re: Stop Telling Students Recursion is Hard

#64

Post by neutronicus »

_3ex7 wrote: post #9
teach wrote: post #7

Earlier quoted context omitted.

I usually show them a recursive Towers of Hanoi solver. It's alarmingly simple (fewer than 10 LOC) and most of them can't even imagine how to write it iteratively. I tell them that recursive code is rarely better than iterative code, but for certain types of problems, it's SO much easier to come up with a recursive solution that it's worth knowing how to do.

I am not sure if I understand recursion or not. My definition of recursion is a function that calls itself repeatedly until an exit condition occurs (the first chapters of little schemer define this as an empty list). If the exit condition never occurs, and the computer lacks infinite computing power, you will probably get a stack overflow. As far as I can tell, recursion and a for-loop accomplish the same thing. Am…

I think you're forgetting that the function can have more than one recursive call site within its body. A for-loop is identical to a recursive function containing only one call site within its body.

By contrast, in order to calculate the number of nodes in a binary tree, you would do

    (nodes (tree)
        (if (tree? tree)
            (1+ (nodes (left-node tree))
                (nodes (right-node tree)))
             0))
which is not like a simple for loop at all.

Re: Stop Telling Students Recursion is Hard

#65

Post by papercrane »

dkarl wrote: post #30

Recursion is a natural idea. When humans perform repetitive tasks, we don't assign state variables, and we generally don't keep counters. We just keep doing the same thing over and over until we arrive at some kind of terminating condition. That's a while loop. To eat a bowl of Cheerios, keep spooning Cheerios into your mouth while there are more Cheerios in the bowl. Telling students that recursion is hard isn't a g…

Recursion is a natural idea. When humans perform repetitive tasks, we don't assign state variables, and we generally don't keep counters. We just keep doing the same thing over and over until we arrive at some kind of terminating condition.

That's a while loop.

Or tail-recursion. I think a more natural example of recursion would be solving a maze. To solve the maze we pick a path we think likely to lead to the exit, if we reach a dead end we back track and try another path.

Re: Stop Telling Students Recursion is Hard

#66

Post by Cushman »

brlewis wrote: post #63
dkarl wrote: post #30

Recursion is a natural idea. When humans perform repetitive tasks, we don't assign state variables, and we generally don't keep counters. We just keep doing the same thing over and over until we arrive at some kind of terminating condition. That's a while loop. To eat a bowl of Cheerios, keep spooning Cheerios into your mouth while there are more Cheerios in the bowl. Telling students that recursion is hard isn't a g…

I've been hearing experienced programmers opine for a long time that while is the more natural representation of repetitive tasks. Twelve years ago my oldest was learning to walk upstairs. I watched her say "up", go up one stair, then say "up" again, and go up the next stair. This concrete example of recursively calling the "up" function did more to convince me that recursion is natural than any explanation with abst…

As pointed out in your parent, that still seems like a loop— wouldn't recursion have been your daughter saying "climb the stairs" before each step?

Re: Stop Telling Students Recursion is Hard

#67

Post by brlewis »

Cushman wrote: post #66
brlewis wrote: post #63

Earlier quoted context omitted.

I've been hearing experienced programmers opine for a long time that while is the more natural representation of repetitive tasks. Twelve years ago my oldest was learning to walk upstairs. I watched her say "up", go up one stair, then say "up" again, and go up the next stair. This concrete example of recursively calling the "up" function did more to convince me that recursion is natural than any explanation with abst…

As pointed out in your parent, that still seems like a loop— wouldn't recursion have been your daughter saying "climb the stairs" before each step?

She was too young for sentences. For her, "up" was not some standard library function she could call from a loop. It was the very procedure she was in the middle of defining.

  (define (up)
     (and (stair-in-front-of-me)
          (walk stair)
          (up)))

Re: Stop Telling Students Recursion is Hard

#68

Post by Cushman »

brlewis wrote: post #67
Cushman wrote: post #66

Earlier quoted context omitted.

As pointed out in your parent, that still seems like a loop— wouldn't recursion have been your daughter saying "climb the stairs" before each step?

She was too young for sentences. For her, "up" was not some standard library function she could call from a loop. It was the very procedure she was in the middle of defining. (define (up) (and (stair-in-front-of-me) (walk stair) (up)))

That's certainly a way of representing it. But surely it's equivalent in practice (as long as the next step can't be a nested flight of stairs) to the iterative approach:

  while there are stairs in front of me
      climb one stair
I guess it's just not as clear to me as it is to you that the "up" utterance is associated with the "climb the stairs" procedure rather than the "climb one stair" procedure.

Re: Stop Telling Students Recursion is Hard

#69

Post by brlewis »

Cushman wrote: post #68
brlewis wrote: post #67

Earlier quoted context omitted.

She was too young for sentences. For her, "up" was not some standard library function she could call from a loop. It was the very procedure she was in the middle of defining. (define (up) (and (stair-in-front-of-me) (walk stair) (up)))

That's certainly a way of representing it. But surely it's equivalent in practice (as long as the next step can't be a nested flight of stairs) to the iterative approach: while there are stairs in front of me climb one stair I guess it's just not as clear to me as it is to you that the "up" utterance is associated with the "climb the stairs" procedure rather than the "climb one stair" procedure.

I agree that it's equivalent in practice; both programs could compile to the same machine code. Where it's different is the human thinking represented by the two programs.

The word "while" implies thinking about a range of time from beginning to end. In contrast, the non-"while" version lets you stay in the moment. It's a conceptually simpler program, up until the point we use that fancy mathematical r-word to describe it.

Re: Stop Telling Students Recursion is Hard

#70

Post by silentbicycle »

dublinclontarf wrote: post #41
silentbicycle wrote: post #36

Earlier quoted context omitted.

Yes, recursion is tied up with baggage about stack allocation. If recursion is approached as inductive reasoning, those objections never occur. This particularly applies to tail-call optimizations and continuations. If somebody isn't thinking in terms of implementations, continuations are just "you pass in who to return the result to, as an argument." e.g. If it succeeds, tell this function the result, otherwise tell…

Why that is the best simple explanation of continuations I have come across yet. Totally right, it's like thinking about how you are able to walk, if you do it trips you up. Dont think about the details just the concepts.

It's not something people are used to talking explicitly about; it's so ingrained that stuff returns directly to what called it that it never occurs to them.

Exceptions are probably the only exception, but I'm not aware of any language besides Common Lisp where an error doesn't unwind the stack - "an exception makes it return several levels up, where the last handler was defined" still fits within a fundamentally stack-based mental model.

Post reply on HN