function - Scheme中的尾递归幂函数

Question

我在方案中编写尾递归幂函数时遇到问题。我想使用辅助函数编写函数。我知道我需要一个参数来保存累积值，但在那之后我被卡住了。我的代码如下。

(define (pow-tr a b)
(define (pow-tr-h result)
  (if (= b 0)
     result
     pow-tr a (- b 1))(* result a)) pow-tr-h 1)

我编辑了我的代码，现在它可以工作了。如下：

(define (pow-tr2 a b)
 (define (pow-tr2-h a b result)
  (if (= 0 b)
    result
    (pow-tr2-h a (- b 1) (* result a))))
 (pow-tr2-h a b 1))

有人可以向我解释为什么辅助函数应该与主函数具有相同的参数。我很难想出为什么这是必要的。

score 4 · Accepted Answer

说“辅助函数应该与主函数具有相同的参数”是不正确的。您只需要传递将在每次迭代中更改的参数- 在示例中，指数和累积结果。例如，如果不将基数作为参数传递，这将正常工作：

(define (pow-tr2 a b)
  (define (pow-tr2-h b result)
    (if (= b 0)
        result
        (pow-tr2-h (- b 1) (* result a))))
  (pow-tr2-h b 1))

它之所以有效，是因为内部辅助过程可以“看到”a外部主过程中定义的参数。而且因为基础永远不会改变，我们不必传递它。要了解更多信息，请查看精彩的SICP书中标题为“内部定义和块结构”的部分。

现在您正在使用帮助程序，最好开始使用namedlet，这是一种非常方便的语法，用于编写帮助程序而无需显式编码内部过程。上面的代码等价于：

(define (pow-tr2 a b)
  (let pow-tr2-h [(b b) (result 1)]
    (if (= b 0)
        result
        (pow-tr2-h (- b 1) (* result a)))))

score 0 · Accepted Answer

即使它具有相同的名称，它也不是相同的参数。如果你深入研究解释器正在做什么，你会看到“a”被定义了两次。一次用于本地范围，但它仍然记住外部范围上的“a”。当解释器调用一个函数时，它会尝试将参数的值绑定到形式参数。

您将值通过相当变异的状态传递的原因就像您可能在 algol 家族语言中所做的那样，因为通过不变异状态，您可以使用替换模型来推理过程的行为。在任何时候使用参数调用的相同过程将产生与从其他任何地方使用相同参数调用相同的结果。

在纯粹的函数式风格中，值永远不会改变，而是你不断地用新值调用函数。编译器应该能够在一个紧密循环中编写代码来更新堆栈上的值（尾调用消除）。通过这种方式，您可以更多地担心算法的正确性，而不是充当人工编译器，这实际上是一种非常低效的机器任务配对。

score 0 · Accepted Answer

0

(define (power a b)
  (if (zero? b)
   1
  (* a (power a (- b 1)))))


(display (power 3.5 3))

于 2020-08-03T20:40:10.020 回答

3 回答 3