The Friday Fragment

It's time again for the Friday Fragment: my weekly programming-related puzzle.

This Week's Fragment?

I caught a little grief for inflicting Lisp on readers last week. So I took that (along with sunny evenings, good river water levels, race targets, and a poolside reading list) as a sign to give the Friday Fragment a summer break. I have some ideas for new types of challenges when we pick it up again, so look for its return in the fall. Until then, enjoy the summer!

Last Week's Fragment - Solution

Last week's fragment was a challenge to think inductively and recursively:

Code a factorial function (s-expression) in Lisp or Scheme. For example, (factorial 3) should evaluate to 6. Include unit test scaffolding code.

As mentioned above, the response to coding in Lisp/Scheme wasn't positive. One comment I got was "I'd rather write Esperanto poetry"  (kids these days, can't think outside the box). So I was left to code this one on my own. Here's my implementation:

   (define factorial
         (lambda (n)
             (cond
                 ((< n 0) "n must be non-negative")
                 ((= n 0) 1)
                 (else (* n (factorial (- n 1)))))))

My test/scaffolding code is:

   ; Unit test case helper:
   (define test
     (lambda (x y)
       (cond
         ((equal? x y) "pass")
         (else (list "FAIL - expected: " y " but got: " x)))))

   "Factorial unit tests"
   (test (factorial -1) "n must be non-negative")
   (test (factorial 0) 1)
   (test (factorial 1) 1)
   (test (factorial 3) 6)
   (test (factorial 55) 12696403353658275925965100847566516959580321051449436762275840000000000000)

I used Dr. Scheme (PLT Scheme) for this, which (like most functional programming environments) is optimized for tail recursion. So even large factorials run fast without error. By comparison, recursive factorial functions in C and Java will (depending on argument size, stack size, and/or VM) either take forever or fail with a stack overflow. One solution for these more traditional environments is to convert tail recursion to iteration and avoid the "stack attack" of recursive function calls.