时间戳

首页 > 解决方案 > 在Scheme中进行相互递归的尾调用优化

recursion - 在Scheme中进行相互递归的尾调用优化

问题描述

在为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)))做。我的第一个想法是代码没有针对正确的尾递归进行优化，而我在每个函数中没有一个，而是两个尾调用。所以，我决定简化任务，只考虑正整数，如下所示：

(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 方案中的相互递归函数是否完全优化？
  2. 诊断。有什么方法可以告诉Scheme编译器/解释器确实为相互尾递归优化了函数。那么，如何判断问题出在（不存在）尾递归优化或其他问题上。
  3. 什么是正确的相互尾递归？我的初始代码是否符合优化条件？我的第二次参加有资格吗？

标签： recursionschemetail-recursionmit-schememutual-recursion

解决方案

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

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

  1. 诊断。

增长FTW 的经验订单！

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

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

也可以看看：

  1. 特征。MIT/GNU 方案中的相互递归函数是否完全优化？

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

推荐阅读