5 ms·

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 factori

by hugh3 16y ago

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?

teach 16y ago
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.
- sid0 16y ago
  I tell them that recursive code is rarely better than iterative code As a general statement, this is wrong. Recursive code is almost always better than imperative code in languages designed to encourage recursion -- I'm thinking of functional languages here, of course. Please qualify your statements to your students, lest they get the idea that it is a problem with recursion as a principle rather than a problem with the language they're working in.
- mdg 16y ago
  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 I missing anything? EDIT: I wrote this before reading the article
  - spacemanaki 16y ago
    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)
    - mdg 16y ago
      Thanks for your answer. >Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps. So that is why people make such a big deal about tail-call optimization? Because it prevents stack overflow?
      - sid0 16y ago
        Yes.
  - neutronicus 16y ago
    I think you're forgetting that the function can have more than one recursive call site within its body. A for-loop is identical to a recursive function containing only one call site within its body. By contrast, in order to calculate the number of nodes in a binary tree, you would do (nodes (tree) (if (tree? tree) (1+ (nodes (left-node tree)) (nodes (right-node tree))) 0)) which is not like a simple for loop at all.
TillE 16y ago
Solving a maze is a classic. The recursive solution is the obvious/intuitive one.
- hugh3 16y ago
  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 will love that kind of thing, others will wonder what the hell the point is.
  - zheng 16y ago
    Yes, exactly, recursive descent parsers are what they sound like. I'm not very up on other types of parsers, but this is the kind I learned about, and I would say they are very intuitive. http://en.wikipedia.org/wiki/Recursive_descent_parser http://en.wikipedia.org/wiki/Recursive_descent_parser
  - djjose 16y ago
    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.
  - btilly 16y ago
    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.

by hugh3 16y ago

teach 16y ago

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.

sid0 16y ago
I tell them that recursive code is rarely better than iterative code As a general statement, this is wrong. Recursive code is almost always better than imperative code in languages designed to encourage recursion -- I'm thinking of functional languages here, of course. Please qualify your statements to your students, lest they get the idea that it is a problem with recursion as a principle rather than a problem with the language they're working in.
mdg 16y ago
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 I missing anything? EDIT: I wrote this before reading the article
- spacemanaki 16y ago
  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)
  - mdg 16y ago
    Thanks for your answer. >Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps. So that is why people make such a big deal about tail-call optimization? Because it prevents stack overflow?
    - sid0 16y ago
      Yes.
- neutronicus 16y ago
  I think you're forgetting that the function can have more than one recursive call site within its body. A for-loop is identical to a recursive function containing only one call site within its body. By contrast, in order to calculate the number of nodes in a binary tree, you would do (nodes (tree) (if (tree? tree) (1+ (nodes (left-node tree)) (nodes (right-node tree))) 0)) which is not like a simple for loop at all.

TillE 16y ago

Solving a maze is a classic. The recursive solution is the obvious/intuitive one.

hugh3 16y ago
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 will love that kind of thing, others will wonder what the hell the point is.
- zheng 16y ago
  Yes, exactly, recursive descent parsers are what they sound like. I'm not very up on other types of parsers, but this is the kind I learned about, and I would say they are very intuitive. http://en.wikipedia.org/wiki/Recursive_descent_parser http://en.wikipedia.org/wiki/Recursive_descent_parser
- djjose 16y ago
  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.
- btilly 16y ago
  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.