Getting tail call optimization in mutual recursion in Scheme

Question

While developing a classical exercise piece of code for odd and even functions in MIT/GNU Scheme (rel 9.2), I encountered a problem that my code does not terminate for a big integer value. First, I tested the following code, which processes both positive and negative values:

(define error-message-number "Error. x must be a number")

(define odd?
  (lambda (x)
    (cond 
      ((not (integer? x)) error-message-number)
      ((= x 0) #f)
      ((< x 0) (even? (+ x 1))) ;for negatives
      (else (even? (- x 1)))))) ;if number n is odd then n - 1 is even 

(define even?
  (lambda (x)
    (cond 
      ((not (integer? x)) error-message-number)
      ((= x 0) #t)
      ((< x 0) (odd? (+ x 1))) ;for negatives
      (else (odd? (- x 1)))))) ;if number n is even then n - 1 is odd

The calls (assert (equal? #f (even? 100000000001))) and (assert (equal? #t (odd? -100000000001))) do not terminate on my machine, while, e.g. (assert (equal? #f (even? 1001))) and (assert (equal? #t (odd? -1001))) do. My first thought was that the code is not optimized for proper tail recursion, while I have not one, but two tail calls in each function. So, I decided to simplify the task and make a take for positive integers only, like this:

(define error-message-positive "Error. x must be a nonnegative number")

(define odd-positive?
  (lambda (x)
    (cond 
      ((not (integer? x)) error-message-number)
      ((= x 0) #f)
      ((< x 0) error-message-positive) ;for negatives
      (else (even? (- x 1)))))) ;if number n is odd then n - 1 is even 

(define even-positive?
  (lambda (x)
    (cond 
      ((not (integer? x)) error-message-number)
      ((= x 0) #t)
      ((< x 0) error-message-positive) ;for negatives
      (else (odd? (- x 1)))))) ;if number n is even then n - 1 is odd

But this version does not return either for big integers. So, I have these related questions:

1. Features. Are mutually recursive functions in MIT/GNU Scheme optimized at all?
2. Diagnostics. Is there any way one can tell the functions were indeed optimized for mutual tail recursion by Scheme compiler/interpreter. So, how can one tell the problem is in (absence of) tail recursion optimization, or in some other thing.
3. What is proper mutual tail recursion? Does my initial code qualify for optimization? Does my second take qualify for it?

Answer 1

3. What is proper mutual tail recursion?

Just like your code, both versions of them.

2. Diagnostics.

Empirical orders of growth FTW!

Your diagnosis just might be incorrect. In particular, on my machine, in Racket, the expected time of your code to finish is 40 minutes. And it does seem to run in constant memory overall.

Yes, even while running in constant space it still takes time linear in the magnitude of argument. How do I know? I simply measured it in clock wall time, and it indeed scales as linear i.e. n¹ power law. Approximately. (i.e. whether it measured as 1.02 or 0.97, it still indicates linear growth rate. approximately. which is all that matters).

See also:

• Painter puzzle - estimation

1. Features. Are mutually recursive functions in MIT/GNU Scheme optimized at all?

It must be so, since tail call optimization is in the language specification. And TCO is more than just tail recursion, as I understand it even if the decision what to call next is dynamic (let alone static, evident in code as it is in your case) it still must run in constant stack space when one tail call eventually leads back to entering the same function again. Tail call is tail call, whatever is called, and it must be optimized. I don't have an official quotation ready at the moment.