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.
I love it!
This is not a tail recursive function. And the biggest example above only uses 55 stack frames so would be fine in most language implementations (assuming the support arbitrarily large integers).
Good point, Robby. Actually, you make three good points:
– Tail recursion. I was using the term in a general sense (meaning the recursive call was the last thing in my function), but maybe the way I wrote it fell short of that. Perhaps order of evaluation meant that it isn’t strictly last; clearly, I’m not a Lisp expert. Dr. Scheme did optimize it to run wickedly fast, so that fed my assumption. Perhaps you can clarify why it isn’t.
– Arbitrarily large integers. That’s often a bigger concern than blowing the stack when using numeric data types in conventional languages. For example, I whipped up a quick C test and it overflowed its unsigned long after 20 factorial.
– It takes more than 55 to blow a stack. I stopped my test cases at 55 because larger numbers were ugly to look at, kinda like the national debt. But, yes, it takes more than 55 frames to blow most stacks. I could get GCC with tiny defaults to overflow at 66 calls, after disabling tail/sibling call optimization. VA Smalltalk overflowed at 2170 factorial. Dr. Scheme and Pharo/Squeak never overflowed in my tests (through 99999 factorial), likely because they optimized tail calls. Running numbers larger than that took longer than I was willing to wait.