I’ve been using scheme and racket quite a bit lately, and because I have been playing with functional languages, I have been doing little exercises in solving problems in a more functional approach, which also includes some nice recursion. More specifically, I’ve been trying to think in a more “tail-recursion” approach to take advantage of the scheme systems that are tail-call optimized.
I found this little article, Quicksort: Like You’re 5, which gave a quick implementation- independent demostration of the quicksort algorithm, and being reintroduced to it’s definition, I recongnized it as perfect for recursion! And of course, a good problem for tail-recursion. However, I couldn’t think of how to approach it in a tail recursive manner, so I started by just quickly coding up a quick non-tail recursive version:
(define (quicksort list) (if (or (empty? list) (empty? (rest list))) list (let ([pivot (first list)] [list (rest list)]) (append (quicksort (filter ((curry >) pivot) list)) `(,pivot) (quicksort (filter ((curry <=) pivot) list))))))
I got stumped, I couldn’t think of how to accumulate the results for a tail-call. The block I was stuck on was, “Can you tail-call something that branches?” I couldn’t think of a way, and unsure if it was me being naive or it was just not possible. Quick searches on rosettacode and duckduckgo turned up similar approaches to what I did above.
After a good nights sleep, I finally conceded. So you can’t tail-call two separate branches, but you can compute one-branch and tail-call the other, right? After a little bit of fumbling, I came up with this:
(define (quicksort-tail thelist) (let quick-acc ([tosort thelist] [acc '()]) (if (or (empty? tosort) (empty? (rest tosort))) (append tosort acc) (let* ([pivot (first tosort)] [tosort (rest tosort)] [acc (append `(,pivot) (quicksort-tail (filter ((curry <=) pivot) tosort)) acc)]) (quick-acc (filter ((curry >) pivot) tosort) acc)))))
I haven’t done anything to determine if it’s more time/space efficient, but it works :]
Update: 10-16-2012 I feel pretty dumb about this post. I have been skimming through the newest [unofficial] version of SICP (as I’ve been contemplating making a toy scheme implementation), and while skimming through the section on recursion, I realized why tail-recursion is so important–it’s how you implement iteration. It was a wonderful moment when lots of dangling ends came together to form a strong knot… and then turned around and called me dumb. The final solution is the obvious one as that’s how we iterate through a tree. I essentially arrived at nested iterations in a very convoluted way.