Hacker News Reader

Comment by teach | Hacker News Reader

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.

View on HN

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

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)

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?

Yes.

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.

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.

Reply on news.ycombinator.com