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

41–50 of 111 posts

Re: Stop Telling Students Recursion is Hard

#41

Post by dublinclontarf »

silentbicycle wrote: post #36
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…

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.

Re: Stop Telling Students Recursion is Hard

#42

Post by btilly »

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…

It sounds like your professors suffer from the same problem that many math professors do. Namely lecturing to an imagined audience that is conversant with intellectual debates that the actual audience is entirely ignorant of.

In the case of math professors this results in lectures where the professor gives detailed proofs despite knowing that nobody in the class followed it, you can't dare test it, and the whole class wondered what the point was. Yet the proofs are rigorous and address points that it took mathematicians decades to figure out.

In the case of your CS profs, in the 1980s I imagine that they were coming out of an era where many computer languages did not support recursion at all because doing so was too inefficient. And therefore they focused very much on exactly how you could implement them, and what the efficiency was.

Re: Stop Telling Students Recursion is Hard

#43

Post by derleth »

hugh3 wrote: post #21
TillE wrote: post #17

Earlier quoted context omitted.

Solving a maze is a classic. The recursive solution is the obvious/intuitive one.

Again, mazes and Towers of Hanoi are neat, but still not exactly what you'd call problems with real-world applicability. There must be some out there -- some types of parsers, perhaps? Are there any matrix operations which are best done recursively? I just think that recursion falls into the category of things that professors think are neat rather than the category of things that are useful to students. Some students…

Try writing a program that does complex things with trees (directory structures, for example) without using recursion.

Re: Stop Telling Students Recursion is Hard

#44

Post by rimantas »

athom wrote: post #33
jchonphoenix wrote: post #10

A lot of the disagreement here comes from what people consider recursion. As in all things, the basic idea behind recursion is quite simple to understand. It's just a function calling itself. There are, however, some non-trivial uses of recursion such as quicksort and analyzing its runtime. Thus, to say simple recursion isn't hard is true. But I'm sure that we can all find a recursive problem that we wouldn't conside…

Actually, this is not correct. While recursion is typically implemented in the form of a function which calls itself, that is not exactly what recursion means. In fact, "recursion" derives from "recur", which simply means to repeat, or re-occur, which, when you look at it, is exactly what a "recursive" function is designed to do (without all that messy for/next, do/while jazz). Calling itself is just a particularly c…

Sound like your definition of recursion fits any loop. I doubt that's what recursion means in CS.

Re: Stop Telling Students Recursion is Hard

#45

Post by rimantas »

cdavid wrote: post #12
jchonphoenix wrote: post #10

A lot of the disagreement here comes from what people consider recursion. As in all things, the basic idea behind recursion is quite simple to understand. It's just a function calling itself. There are, however, some non-trivial uses of recursion such as quicksort and analyzing its runtime. Thus, to say simple recursion isn't hard is true. But I'm sure that we can all find a recursive problem that we wouldn't conside…

Agreed - the problem is not recursion, but that it becomes useful for actual complex problems. I understand recursion pretty well at a conceptual level (my background is math, mostly self-taught for CS), but I have a hard time using it for programming. Sure, fibonacci or quicksort are simple, but tree recursion or application to string processing (e.g. for edit distance compuation) is quite harder.

I am the only one who gets upset when fibonacci sequence calculation is used as an example of recursion? Are there other possible examples which are simpler than quicksort, but actually make sense if done with recursion instead of simple loop?

Re: Stop Telling Students Recursion is Hard

#46

Post by cabalamat »

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…

> but telling them that it's a familiar idea that they already implicitly understand isn't a good idea either.

But people do implicitly understand recursion. Your ancestors are your parents and their ancestors. Your descendants are your children and their descendants. Most people understand the previous two sentences.

> As soon as they figure out that for and while loops are sufficient to express all the programming ideas they can come up with

There are plenty of problems for which recursion is the most natural solution. For example, building HTML for nested comments is easy with recursion and damned difficult without.

Re: Stop Telling Students Recursion is Hard

#48

Post by athom »

rimantas wrote: post #44
athom wrote: post #33

Earlier quoted context omitted.

Actually, this is not correct. While recursion is typically implemented in the form of a function which calls itself, that is not exactly what recursion means. In fact, "recursion" derives from "recur", which simply means to repeat, or re-occur, which, when you look at it, is exactly what a "recursive" function is designed to do (without all that messy for/next, do/while jazz). Calling itself is just a particularly c…

Sound like your definition of recursion fits any loop. I doubt that's what recursion means in CS.

This is why most looping structurues can be replaced with recursion. It's also why you hear of "unrolling" tail-recursive calls into more traditional looping structures. They're equivalent.

Re: Stop Telling Students Recursion is Hard

#49

Post by ay »

cabalamat wrote: post #46
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…

> but telling them that it's a familiar idea that they already implicitly understand isn't a good idea either. But people do implicitly understand recursion. Your ancestors are your parents and their ancestors. Your descendants are your children and their descendants. Most people understand the previous two sentences. > As soon as they figure out that for and while loops are sufficient to express all the programming…

Another algorithm which is much simpler in its recursive form is a flood-fill - paint the screen area with a given color till you hit a "border".

Re: Stop Telling Students Recursion is Hard

#50

Post by cousin_it »

hugh3 wrote: post #21
TillE wrote: post #17

Earlier quoted context omitted.

Solving a maze is a classic. The recursive solution is the obvious/intuitive one.

Again, mazes and Towers of Hanoi are neat, but still not exactly what you'd call problems with real-world applicability. There must be some out there -- some types of parsers, perhaps? Are there any matrix operations which are best done recursively? I just think that recursion falls into the category of things that professors think are neat rather than the category of things that are useful to students. Some students…

If you're writing a 3d engine, you may encounter many tree-like structures and recursive operations on them: BSPs, quadtrees, octrees, triangle trees for variable LOD terrain...
Post reply on HN