Chad Perrin: SOB

23 August 2009

If I Was Better

Filed under: Cognition,Geek — apotheon @ 08:21

I suspect that if I was a better programmer:

  1. I would use more recursion in Perl.

  2. I would use more iteration in Scheme.

In April 2008, under the title recursion confessional, I discussed the fact that my mastery of the Force recursion was less than complete (to put it mildly). This is changing as I work more with Scheme, fighting through the exercises in SICP.

I suspect this will lead to a much more complete and natural understanding of recursion in the context of programming for “real world” purposes in the future. For reasons pointed out in recursion confessional, however, chances are good that I still won’t use it very much for my everyday programming needs for a while, since most of my programming is still likely to involve Perl and Ruby (and, unfortunately, some PHP when I can’t avoid it). The way Scheme itself so readily lends itself to recursive solutions to programming problems is of tremendous help with making it feel more natural, and less like an academic chore.

In fact, I find myself in what seems like a pretty odd position with regard to my programming proclivities right now: when I hack out a solution to a repetitious programming problem in Perl or Ruby, the obvious answer is iterative (especially given Ruby’s iterator constructs); when I tackle a repetitious programming problem in Scheme, however, I come up with a recursive solution first and most naturally. The oddest part of this situation, though, is the fact that when I’m writing code in Scheme, once I’ve come up with the obvious recursive solution, I have difficulty even formulating an iterative solution.

Part of the discussion of recursion in recursion confessional centered around Dan Kegel’s How To Get Hired — What CS Students Need To Know. One of three key competencies he identified for programmers — things that should be high on the list of skills to test as an interviewer — is practical recursion. As I said at the time I wrote recursion confessional, I probably wouldn’t have passed his interview at the time. Now, I think I might, if that’s all that was really tested (the ability to make practical use of recursion to solve real programming problems).

The problem that still lingers appears to be that I find it difficult, for the moment, to use recursion in a programming context that is designed more with iteration in mind, and to use iteration in a programming context that is designed more with recursion in mind. When I say “use” here, I mean everything from recognizing the usefulness of the technique in question for solving this particular problem to figuring out how to actually formulate a solution for that particular problem using the technique in question.

I expect that to change as I work more with Scheme, and as I do more “real world” coding in Perl and Ruby after having encountered recursion in the context of Scheme. It just takes practice, and (as I mentioned in recursion confessional) I’m a fast learner. I just felt like lamenting the fact that I utterly failed at coming up with an iterative solution to a problem in SICP after having already solved it recursively. I suppose I could have taken that as a good sign, though, since the solution that came to me quite naturally had a far more elegant form than the iterative solution — but giving myself credit for that would be cheating.

Anyway . . . all of this is why I suspect I’d use more recursion in Perl and more iteration in Scheme if I was a better programmer. I get a free pass for Ruby, though, because it (version 1.8.x) doesn’t do tail-call optimization and doesn’t appear to have anything up to the standards of Perl’s Memoize module. As such, it’s just a bad idea to do much recursion in Ruby anyway. Thank goodness for Ruby’s do-end iterators.

addendum: Posts about code should usually have code in them. The following are the recursive and iterative solutions to an SICP exercise that demonstrate my above point. In the case of the exercise for which these functions serve as solutions, the recursive solution just poured through my fingers into the keyboard. Meanwhile, I completely failed to see the iterative solution until I got away from the problem for a while and looked at other iterative solutions to programming problems in Scheme (such as an iterative Fibonacci function).

(define f
  (lambda (n)
    (if (< n 3)
        (+ (f (- n 1))
           (* 2 (f (- n 2)))
           (* 3 (f (- n 3)))))))
(define f
  (lambda (n)
    (define fi
      (lambda (a b c i)
        (if (= i 0)
            (fi (+ a (* 2 b) (* 3 c))
                (- i 1)))))
    (fi 2 1 0 n)))

There are surely better solutions for both approaches, of course, but I did the minimum and, unless I feel inspired, won’t bother improving either for now.

1 Comment

  1. That’s an interesting take on it, and I agree. Recursion often gets over-used in Lisp dialects, and underutilized in most other languages. I find recursion to be most useful when processing nested data structures, like elements in an OPML file parser, or parenthesized expressions in an interpreter. When the data is fractal, then recursion provides a correspondigly fractal model for consuming or generating it.

    Comment by Chip Camden — 25 August 2009 @ 02:45

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

All original content Copyright Chad Perrin: Distributed under the terms of the Open Works License