是作爲尾遞歸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指令嗎？

回答

相關問題