Am I along in never being "taught" recursion? I mean, throughout my curriculum, I've used recursion many times and dealt with everything from fibonacci to quicksort, but never once have I sat through even part of a lecture on "Recursion". Among my peers, I don't think anyone really has an issue with recursion or how it works. Harder to debug possibly, but everyone "gets" it, I feel.
Stop Telling Students Recursion is Hard
11–20 of 111 posts
Re: Stop Telling Students Recursion is Hard
#12A 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.
Re: Stop Telling Students Recursion is Hard
#13Interesting article on recursion...
http://tenaciousc.com/?p=1000
Re: Stop Telling Students Recursion is Hard
#14It 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.
Re: Stop Telling Students Recursion is Hard
#15Getting tail recursion right IS hard.
Re: Stop Telling Students Recursion is Hard
#16Interestingly 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".
Re: Stop Telling Students Recursion is Hard
#17Earlier quoted context omitted.
The idea behind recursion is I have X, if I know Y then this would be easy. But, picking the correct Y and finding a simple path to get Y is hard for many people. Consider something as simple as factorials. 1! = 1 and N! = N * N-1! but try to code it as: N! = N! / 1! * 1 = N! / 2! * 2 = N! / 3! * 6. Then with a lot of time and effort they get something that works, but it's not intuitive.
Perhaps the other problem is that it's not obvious to students what the point of doing things recursively is. OK, it can shave a few characters off your factorization code. Or your Fibonacci code. That's neat, but why get excited?
Solving a maze is a classic. The recursive solution is the obvious/intuitive one.
Re: Stop Telling Students Recursion is Hard
#18On 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/Exponentiation -- it's iteration, pure and simple. And in most non-functional languages, it's trivial to implement that way, and will probably be more efficient than a recursive solution.
Re: Stop Telling Students Recursion is Hard
#19It's funny. I've JUST finished spending a week or so on recursion with my students. The FIRST thing I did was have the entire class repeat after me: "Recursion isn't hard. It's just different." And I've been teaching CS at the high-school level for 13(?) years now, and I've never had a student who just couldn't get recursion. On the contrary, most of the them pick it up pretty quickly. There's initial confusion, foll…
As a programmer of more than a decade who fell in love with CS in high school, thank you for teaching the topic to others!
Re: Stop Telling Students Recursion is Hard
#20Earlier 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…
You aren't missing anything, but recursion can get more complicated. In the case of towers of Hanoi, or recursion on trees, the iterative version using a for-loop becomes substantially more complicated than the recursive version.
Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps. So in Scheme this will actually produce an infinite loop with no stack overflow:
(define (loop)
(loop))
(loop)