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

51–60 of 111 posts

Re: Stop Telling Students Recursion is Hard

#51

Post by roel_v »

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…

Graph problems would be hard without recursion I think. I've been working on some problems that are naturally expressed as graphs, and recursion is the natural way to do some things; it's be quite hard to do some things I did iteratively, now that I think about it (that is, without 'emulating' recursion with an 'explicit', manually-maintained stack).

Re: Stop Telling Students Recursion is Hard

#52

Post by ern »

grigory wrote: post #22

In my first year programming course, our prof spent 10-15 minutes at most talking about recursion. I was already familiar with it, but my classmates (mostly non-CS majors) had no problems understanding the concept. Since that experience I'm always slightly amused when I hear people saying that teaching basics of recursion is hard. Perhaps it isn't taught properly? When you're just starting out with it, there really i…

You say they "understood" the concept. Was this understanding tested in some way?

Re: Stop Telling Students Recursion is Hard

#53

Post by merijnv »

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.

That would be because recursion and loops are isomorphic. Anything you can do with recursion can be done in a loop and vice versa. It's just that one or the other may be clearer or easier depending on what you're doing.

Re: Stop Telling Students Recursion is Hard

#54

Post by arethuza »

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…

I'd have said quicksort is an example of an algorithm where the easiest way to think of is recursively.

Re: Stop Telling Students Recursion is Hard

#55

Post by adrianN »

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…

When I have to eat a whole bowl of Cheerios, I'm usually overwhelmed by its size. So I try eating just a spoonful. Lo' and behold, there are less Cheerios now, but still too many to eat them all at once. So I try just another spoonful...

Re: Stop Telling Students Recursion is Hard

#56

Post by Retric »

btilly wrote: post #35
hugh3 wrote: post #21

Earlier quoted context omitted.

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…

Any "divide and conquer" algorithm is likely to be recursive. Thus, for instance, the FFT, the Karatsuba multiplication algorithm for large integers, Strassen's matrix multiplication algorithm for matrices and the like are all recursive. Moving on, dynamic programming is a very important technique. About half the time it is easier for me to figure out a dp solution by writing a recursive solution with memoization tha…

You can talk about "divide and conquer" but the most common problem where recursion really helps is looking at tree data structures. As then to consider looking for the total of some value stored in an XML tree.

In an iterative language it's a for loop and then calling the function on each of the children. In a Lisp it's calling it's self on the child and next node.

PS: Showing someone they can transform a recursion function into a while loop if they keep track of their own stack seems to help. Yea, you can write it that way, but recursion really is simpler. (This also helps explain what a stack really is.)

Re: Stop Telling Students Recursion is Hard

#57

Post by adrianN »

d135-1r43 wrote: post #47

Telling them that it is cost intensive would be better!

That depends on how you write your recursion, what your compiler does with it and what you use as cost function (programmer productivity?). That's too many 'depends' to tell students about, I think.

Re: Stop Telling Students Recursion is Hard

#58

Post by fferen »

jinfiesto wrote: post #28
colomon wrote: post #18

On the one hand, I'm in total agreement that we shouldn't tell students recursion is hard. It's a very natural analog to proof by induction, after all. It's an important basic component of programming. On the other hand, "IMHO, recursion is much more natural than iteration and ought to be taught first" is just nuts. I mean, look at the first definition of his example function at http://en.wikipedia.org/wiki/Exponenti…

I don't think the example I've given is iterative. It generates a recursive process. You're right on a different point though, this example is much more efficiently implemented iteratively. The point was to illustrate that writing recursive functions is not difficult. I guess we don't see eye to eye on recursion being taught first. :p In my opinion, recursions analog to "the real world" is much more intuitively obvio…

I think parent was referring to the definition on the Wikipedia page:

"When n is a positive integer, exponentiation corresponds to repeated multiplication."

And then an equation that suggests an iterative approach.

Re: Stop Telling Students Recursion is Hard

#60

Post by delinka »

colomon wrote: post #18

On the one hand, I'm in total agreement that we shouldn't tell students recursion is hard. It's a very natural analog to proof by induction, after all. It's an important basic component of programming. On the other hand, "IMHO, recursion is much more natural than iteration and ought to be taught first" is just nuts. I mean, look at the first definition of his example function at http://en.wikipedia.org/wiki/Exponenti…

int pow(int b, int e) { return b * ((e==1)?1:pow(b,e-1)); }
Post reply on HN