Hacker News Reader

Comment by jchonphoenix | Hacker News Reader

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 consider easy.

View on HN

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?

No, I think it is a terrible example at so many levels it is not even funny. The only interesting thing about that example is how almost any other solution is much better.

I would consider quicksort to be a quite simple example if you use a high level language. But search in binary search tree and similar tree/graph traversal are maybe better examples, in the sense that most people would find recursion to be more natural than any iterative solution.

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

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.

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.

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.

Reply on news.ycombinator.com