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

31–40 of 111 posts

Re: Stop Telling Students Recursion is Hard

#31

Post by djjose »

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…

One of the projects in my CS program using recursion was a 6-degrees of Kevin Bacon game. It was neat and real-world practical IMO.

Re: Stop Telling Students Recursion is Hard

#32

Post by leif »

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 for loops and increments and a bunch of returns all through it, this is the real stuff, remember it!" We un-teach them about recursion, and later, when we try to re-teach it to them, we have to undo all of our previous work.

In the past, there was considerable merit to un-learning the inefficient definition-style functions and learning to think closer to the machine. Today, I think there's a lot more to be gained by sticking with the math-style function-as-a-definition, because we have efficient abstractions to deal with it, but of course, this is one of the friendliest forums for that sort of philosophy.

FWIW, I propose that all of academia make a distinction between pure, recursive, definition-style "functions", and imperative, stateful "methods". Probably won't catch on :-/

Re: Stop Telling Students Recursion is Hard

#33

Post by athom »

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 clever, interesting, and elegant way to do that.

To really illustrate the point of recursion, consider showing your students one of the simplest recursive algorithms out there. You can find it on the back of many shampoo bottles:

  * Lather.
  * Rinse.
  * Repeat.

Re: Stop Telling Students Recursion is Hard

#35

Post by btilly »

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…

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 than it is to build the solution bottom up.

The single most studied problem in computer science is sorting, for the simple reason that a surprising fraction of computing time spent is spent doing sort operations. Virtually every efficient sort algorithm uses recursion somewhere.

The fact that a lot of students won't go on to use recursion doesn't mean that it isn't a very useful technique.

Re: Stop Telling Students Recursion is Hard

#36

Post by silentbicycle »

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 this function the error.

Yet another case of making concepts hard by knowing too much.

Re: Stop Telling Students Recursion is Hard

#37

Post by mzl »

When teaching our students concurrent programming using Erlang we never actually mentioned recursion and state immutability. With some careful hand-holding in the first exercises, most of the students seemed to be able to do fine. During three years of teaching the class, only two students ever asked me about immutability ("why can't I change the value of this variable?"). Recursion went similarly unnoticed, it was just the way one programmed in Erlang. Still, a lot of the code produced in the assignments was not very good, but that is to be expected from the course level and the students.

There are two main reasons why I think that most students picked it up without too big troubles. First is that we are just using these things as part of a language while focusing on other topics (concurrent programing). The other is that Erlang is language with such a different syntax from the normal Java-fare that one naturally expects to not be able to do things in the same way.

Post reply on HN