是作为尾递归goto指令吗？

我发现下面的执行二进制搜索的方案：是作为尾递归goto指令吗？

(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))))))

根据它所在评论中说，上述函数使用尾递归调用的帮助功能。我想知道这是否像GOTO指令一样工作，因为我没有看到对二进制搜索函数有适当的“递归”调用。

在这种情况下，说它适合像goto指令吗？

来源

2014-11-03 Layla

你所看到的名字叫做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跳转到代码中的一个任意点，但它完全是命令式的操作，与递归无关。

来源

2014-11-03 00:18:50

谢谢，那么你是说真的在这里进行递归的函数是对辅助函数的调用吗？ – Layla 2014-11-03 03:05:22

@Layla是的。 :-) – 2014-11-03 04:05:34

一个let只是lambda的语法糖。因此，例如：

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

相当于

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

在你的代码的让利被称为一个名为让利，因为你为它提供了一个标签。所以基本上，你变相的lambda绑定了一个名字。从这个意义上讲，这是一个转折点。但是，您需要处于let的范围内才能够“跳跃”到它。该函数是尾递归的，因为你不推迟任何计算。在任何时间点，您只需要i和j的当前值即可继续进行计算。

来源

2014-11-03 00:29:53 turingcomplete

是作为尾递归goto指令吗？

回答

相关问题