时间戳

首页 > 解决方案 > 重新定义`if`时无休止的递归，为什么？

scheme - 重新定义`if`时无休止的递归，为什么？

问题描述

我是编程新手，开始学习语言方案。（我研究了《计算机程序的结构和解释》一书），遇到了一项任务，如下所述。我写了两个代码替换if为cond，但是由于某种原因，在运行第一个代码时存在无限递归，但是在运行第二个代码时没有无限递归，它通常会计算sqrt ...虽然代码是相同的，为什么会这样?

Alyssa P. Hacker 不明白为什么if需要以特殊形式提供。“为什么我不能把它定义为一个普通的程序cond？” 她问。Alyssa 的朋友 Eva Lu Ator 声称这确实可以做到，她定义了一个新版本if：

(define (new-if predicate then-clause else-clause)
    (cond (predicate then-clause)
        (else else-clause)))

Eva 演示了 Alyssa 的程序：

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

很高兴，Alyssa 用它new-if来重写square-root程序：

(define (sqrt-iter guess x)
    (new-if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x)
        x)))

当 Alyssa 尝试使用它来计算平方根时会发生什么？解释。

第一个代码：

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (square x)
  (* x x))

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (better-good-enough? prev-guess guess)
  (< (abs (- guess prev-guess))
     0.00001))

(define (better-sqrt-iter prev-guess guess x)
  (new-if (better-good-enough? prev-guess guess)
      guess
      (better-sqrt-iter guess
                        (improve guess x)
                        x)))

(define (better-sqrt x)
  (better-sqrt-iter 0 1.0 x))

第二个代码：

(define (square x)
  (* x x))

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (better-good-enough? prev-guess guess)
  (< (abs (- guess prev-guess))
     0.00001))

(define (better-sqrt-iter prev-guess guess x)
  (cond ((better-good-enough? prev-guess guess)
      guess)
        (else (better-sqrt-iter guess
                        (improve guess x)
                        x))))

(define (better-sqrt x)
  (better-sqrt-iter 0 1.0 x))

标签： schemeconditional-statementslispinfinite-loopevaluation

解决方案

这听起来像是一个家庭作业问题，但是，假设您使用的是 Scheme，请考虑当一般形式（所以，不是任何特殊形式）像

(f a b c)

被评估：

  1. f, a, b&c以某种未定义的顺序进行评估（甚至可能同时进行）；
  2. 应该是一个函数的f（换句话说，评估它的结果）的值应用于评估的结果a，b& c;
  3. 该函数返回一个值（或多个值），这是表单的值。

当您使用此评估策略尝试评估 的第一个版本时会发生better-sqrt-iter什么？您可以用纸和铅笔手工进行一些评估，看看会发生什么。

为什么该评估规则在这里存在问题？

推荐阅读