let在尾递归中是作为goto指令工作的吗？

Question

我在Scheme中找到了二进制搜索的以下实现：

(define (binary-search value vector)
  (let helper ((low 0)
               (high (- (vector-length vector) 1)))
    (if (< high low)
        #f
        (let ((middle (quotient (+ low high) 2)))
          (cond ((> (vector-ref vector middle) value)
                 (helper low (- middle 1)))
                ((< (vector-ref vector middle) value)
                 (helper (+ middle 1) high))
                (else middle))))))

根据它在注释中的说明，上面的函数使用尾递归来调用help函数。我想知道这是否像GOTO指令一样工作，因为我没有看到对二进制搜索函数的适当的“递归”调用。

在这种情况下，可以说它像goto指令一样工作？

Answer 1

您看到的内容称为命名let。(如果你感兴趣，我写了一个blog post about how named let works。)您拥有的代码与以下代码完全相同：

(define (binary-search value vector)
  (define (helper low high)
    (if (< high low)
        #f
        (let ((middle (quotient (+ low high) 2)))
          (cond ((> (vector-ref vector middle) value)
                 (helper low (- middle 1)))
                ((< (vector-ref vector middle) value)
                 (helper (+ middle 1) high))
                (else middle)))))
  (helper 0 (- (vector-length vector) 1)))

换句话说，它是尾递归，在helper上，而不是在binary-search上。但是尾部递归正在发生。

有些人认为尾递归类似于goto，但我不认为这是一个有帮助的比较。两者之间唯一的共同点是，您可以使用尾递归实现循环，就像您可以使用goto一样。但相似之处到此为止:尾递归是一种特殊的递归(用尾部调用替换当前调用帧)，但它仍然是递归；goto跳到代码中的任意点，但它是与递归无关的完全命令式操作。

Answer 2

let只是lambdas的语法糖。举个例子：

(let ((i 2)
      (j 5)
  (* i j))

等同于

((lambda (i j) (* i j)) 2 5)

代码中的let称为命名let，因为您为它提供了标签。所以基本上，你伪装的lambda与一个名字绑定在一起。从这个意义上说，它是一个goto。但是，您需要在let的作用域中才能“跳转”到它。该函数是尾递归的，因为您没有延迟任何计算。在任何时间点，您只需要i和j的当前值即可继续进行计算。