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

71–80 of 111 posts

Re: Stop Telling Students Recursion is Hard

#71

Post by colomon »

fferen wrote: post #58
jinfiesto wrote: post #28

Earlier quoted context omitted.

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.

Exactly. Good catch.

Re: Stop Telling Students Recursion is Hard

#72

Post by eru »

leif wrote: post #32
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…

Why, though, do they think of a function as a machine for doing something? Because we tell them so. Before starting any standard CS curriculum (ignoring, for a moment, self-taught hackers), the only place a student should have heard about "functions" is in math class---where they are definitions. They get to intro Java and we tell them "no, no, that's not a function, this is a function, look, it's got variables and f…

Your "methods" have also been called "procedures".

Re: Stop Telling Students Recursion is Hard

#73

Post by eru »

sirclueless wrote: post #61
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…

I just tried, and ghci (i.e. Haskell) does not blow up when confronted with

    > let f n = if n > 0 then n + f (n - 1) else 0
    > f 1000000

Re: Stop Telling Students Recursion is Hard

#74

Post by colomon »

delinka wrote: post #60
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)); }

Yes, the author defines exponentiation in terms of recursion. My point is that is not the natural definition of exponentiation, and my evidence is the Wikipedia page, which (as of the time of my original posting of the link, anyway), gives an iterative definition of exponentiation first -- the exact same one I learned in grade school -- and then several pages later mentions a recursive definition as a one-sentence aside.

Re: Stop Telling Students Recursion is Hard

#75

Post by eru »

Sherlock wrote: post #62
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.

I heard Matthias Felleisen saying the same.

Re: Stop Telling Students Recursion is Hard

#76

Post by eru »

roel_v wrote: post #51
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…

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

Yes. Though breadth-first approaches look much more imperative than depth-first traversals. That's because basically you exchange the stack for a queue. (Those algorithms can still look nice in, say, Haskell.)

Re: Stop Telling Students Recursion is Hard

#77

Post by eru »

arethuza wrote: post #54
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…

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

And while you're at it, quickselect, too.

Re: Stop Telling Students Recursion is Hard

#78

Post by eru »

ohyes wrote: post #14

It might be easier to teach them about functions that can call themselves first; and then explain the concept of recursion in the context of that (or just that it is called 'recursion'). A recursive function call is conceptually no different than a regular function call.

There's more to recursion than functions. Data types (like linked lists) can also be recursive.

Re: Stop Telling Students Recursion is Hard

#79

Post by eru »

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…

> As in all things, the basic idea behind recursion is quite simple to understand. It's just a function calling itself.

That's not the whole story. There's more to recursion than that. You can have mutual recursion, and recursion in things other than functions: e.g. data structures, or the structure of the Mandelbrot set or that of the fern-like fractals.

Re: Stop Telling Students Recursion is Hard

#80

Post by ericmoritz »

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…

This is the reason why I'm never get excited about recursion. I hardly ever find a real world application for it aside from a tree transversal.

Most examples are toys (fib, towers of hanoi, maze solving) or problems that are already solved, sorting, searching, etc.

Post reply on HN