在Scheme中的相互递归中获得尾调用优化

Question

在为MIT/GNU Scheme (rel 9.2 ) 中的odd和even函数开发经典练习代码时，我遇到了一个问题，即我的代码不会因大整数值而终止。首先，我测试了以下代码，它处理正值和负值：

(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

调用(assert (equal? #f (even? 100000000001)))和(assert (equal? #t (odd? -100000000001)))不会在我的机器上终止，而例如(assert (equal? #f (even? 1001)))和(assert (equal? #t (odd? -1001)))do。我的第一个想法是代码没有针对正确的尾递归进行优化，而我没有一个，而是每个函数中的两个尾调用。因此，我决定简化任务并仅对正整数进行处理，如下所示：

(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

但是这个版本不会返回大整数。所以，我有这些相关的问题：

1. 特征。MIT/GNU Scheme 中的相互递归函数是否经过优化？
2. 诊断。有什么办法可以告诉我们，Scheme 编译器/解释器确实针对相互尾递归优化了这些函数。那么，如何判断问题出在（没有）尾递归优化中，还是出在其他方面。
3. 什么是正确的相互尾递归？我的初始代码是否符合优化条件？我的第二次拍摄是否符合条件？

Answer 1

3. 什么是正确的相互尾递归？

就像你的代码一样，它们的两个版本。

2. 诊断。

FTW 的经验增长顺序！

您的诊断可能不正确。特别是，在我的机器上，在 Racket 中，您的代码完成的预期时间是40 分钟。它似乎确实在整体内存中运行。

是的，即使在恒定空间中运行，它仍然需要与参数大小成线性关系的时间。我怎么知道？我只是用时钟墙上的时间来测量它，它确实是线性的，即n ¹幂律。大约。（即，无论测量为 1.02 还是 0.97，它仍然表示线性增长率。大约。这才是最重要的）。

也可以看看：

• 画家拼图 - 估计

1. 特征。MIT/GNU Scheme 中的相互递归函数是否经过优化？

必须如此，因为尾调用优化在语言规范中。并且 TCO 不仅仅是尾递归，正如我所理解的，即使决定下一步调用什么是动态的（更不用说静态的，在你的情况下在代码中很明显）它仍然必须在一个尾调用时在恒定的堆栈空间中运行最终导致再次进入相同的功能。尾调用就是尾调用，不管叫什么，都要优化。我目前没有准备好正式报价单。