3 ms·

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

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.

cdavid 16y ago
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.
- rimantas 16y ago
  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?
  - cdavid 16y ago
    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.
athom 16y ago
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.
- rimantas 16y ago
  Sound like your definition of recursion fits any loop. I doubt that's what recursion means in CS.
  - athom 16y ago
    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.
  - merijnv 16y ago
    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.
eru 16y ago
> 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.

cdavid 16y ago

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.

rimantas 16y ago
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?
- cdavid 16y ago
  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.

athom 16y ago

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.

rimantas 16y ago
Sound like your definition of recursion fits any loop. I doubt that's what recursion means in CS.
- athom 16y ago
  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.
- merijnv 16y ago
  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.

eru 16y ago

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