Are there problems that cannot be written using tail recursion?

by

Yes, actually you can take some code and convert every function call—and every return—into a tail call. What you end up with is called continuation-passing style, or CPS.

For example, here’s a function containing two recursive calls:

(define (count-tree t)
  (if (pair? t)
    (+ (count-tree (car t)) (count-tree (cdr t)))
    1))

And here’s how it would look if you converted this function to continuation-passing style:

(define (count-tree-cps t ctn)
  (if (pair? t)
    (count-tree-cps (car t)
                    (lambda (L) (count-tree-cps (cdr t)
                                                (lambda (R) (ctn (+ L R))))))
    (ctn 1)))

The extra argument, ctn, is a procedure which count-tree-cps tail-calls instead of returning. (sdcvvc’s answer says that you can’t do everything in O(1) space, and that is correct; here each continuation is a closure which takes up some memory.)

I didn’t transform the calls to car or cdr or + into tail-calls. That could be done as well, but I assume those leaf calls would actually be inlined.

Now for the fun part. Chicken Scheme actually does this conversion on all code it compiles. Procedures compiled by Chicken never return. There’s a classic paper explaining why Chicken Scheme does this, written in 1994 before Chicken was implemented: CONS should not cons its arguments, Part II: Cheney on the M.T.A.

Surprisingly enough, continuation-passing style is fairly common in JavaScript. You can use it to do long-running computation, avoiding the browser’s “slow script” popup. And it’s attractive for asynchronous APIs. jQuery.get (a simple wrapper around XMLHttpRequest) is clearly in continuation-passing style; the last argument is a function.

More Related Contents:

  1. What is tail recursion?
  2. Spanning repeatable keys
  3. What is tail call optimization?
  4. What is a ‘Closure’?
  5. How do I replace while loops with a functional programming alternative without tail call optimization?
  6. What is (functional) reactive programming?
  7. Prolog Accumulators. Are they really a “different” concept?
  8. Does Python optimize tail recursion?
  9. Are functions in JavaScript tail-call optimized?
  10. What is the difference between eq?, eqv?, equal?, and = in Scheme?
  11. What are paramorphisms?
  12. Advantages of stateless programming?
  13. How can you do anything useful without mutable state?
  14. What is ‘Pattern Matching’ in functional languages?
  15. What is the exact definition of a closure?
  16. Generate tail call opcode
  17. Functional programming and non-functional programming
  18. What is Hindley-Milner?
  19. How to understand curry and function composition using Lodash flow?
  20. Implications of foldr vs. foldl (or foldl’)
  21. In Functional Programming, what is a functor?
  22. Does Ruby perform Tail Call Optimization?
  23. Tail Call Optimisation in Java
  24. Does PHP optimize tail recursion?
  25. Python recursive function to display all subsets of given set
  26. How can a time function exist in functional programming?
  27. So: what’s the point?
  28. Convert recursion to tail recursion
  29. Splitting a list of items into two lists of odd and even indexed items
  30. Tail recursion in gcc/g++

Leave a Comment