2尾爲長度[球拍]遞歸函數

我試圖寫計算列表的長度的兩個分離的尾遞歸函數，我考慮到這些限制：2尾爲長度[球拍]遞歸函數

寫版本，lengtht即尾遞歸併根據需要使用外部（非嵌套）輔助功能
編寫第二個版本，lengtht2不使用額外的頂級功能。該功能應該仍然是尾遞歸，並且可以使用您想

我是新來的球拍任何本地綁定，這就是我理解尾遞歸的一般形式是：

(define (func x) 
    (cond (end-test-1 end-value-1) 
      (end-test-2 end-value-2) 
      (else (func reduced-x))))

我只是有點困惑如何做到這一點

來源

2012-10-10 asdfghjkl

http://stackoverflow.com/questions/33923/what-is-tail-recursion –

這看起來像家庭作業，所以我會給你一些提示，指出你在正確的方向，你可以填補空白。試試這個第一個問題：

(define (loop lst acc)    ; receives a list and an accumulator 
    (cond ((null? lst) <???>)   ; if the list is empty return the accumulator 
     (else (loop <???> <???>)))) ; advance the recursion, +1 to accumulator 

(define (length1 lst) 
    (loop <???> <???>))    ; how should we initialize the iteration?

試試這個關於第二個問題：

(define (length2 lst) 
    (letrec ((loop <???>)) ; lambda with the same procedure as the previous `loop` 
    (loop <???> <???>))) ; start the recursion exactly the same as in `length1`

在任何情況下，想了一會兒：什麼是一個空（NULL）列表的長度？答案會告訴你如何初始化迭代。對於這兩種解決方案，我們使用一個名爲acc的額外參數來跟蹤迄今爲止的答案，並將其與列表一起傳遞給循環尾遞歸過程。

來源

2012-10-10 03:46:22

這些過程是等價的，但在使用它們的過程中隱藏輔助函數是一個更好的主意，所以第二種解決方案是首選。第二種解決方案的另一種選擇是使用「命名讓」 –

mmm，我沒有說清楚。你在第二個函數中看到的'loop'只是'lambda'的_name_，你必須定義，並且lambda有兩個參數，就像第一個函數中的'loop'一樣 - 事實上，重新相同的功能。充實更多的細節，'length2'中的第一個應該看起來像這樣：'（lambda（lst acc）...）'。我們使用了'letrec'，因爲'lambda'需要引用它自己，通過名稱'loop'指定它被定義爲 –

是的，填入缺失的'...'部分。幾乎與第一個'loop'相同。 –

本質上，尾遞歸函數不斷調用自己，直到它達到其結束條件。然而，與「常規」遞歸不同，它會傳遞中間答案給自己，直到達到最後。

一個例子是這樣的：

(define (find-length i lst) 
    (if 
    (null? lst) i 
    (find-length (+ i 1) (cdr lst))))

這個函數有兩個值：i，追蹤列表的長度，到目前爲止，lst，我們計算的元素列表。爲了所有的意圖和目的，我們的列表中的元素的運行計數是i。因此，如果我們調用此方法，我們將要用i將其初始化爲0.

首先我們檢查列表是否爲空。（null?）如果列表爲空，我們可以假設我們已經計算了所有元素，所以我們只返回i，這是我們的運行計數。這是我們的最終狀態。

否則，我們再次撥打find-length。但是，這一次，我們將i加1，並從列表(cdr lst)中刪除第一個元素。

例如，假設我們這樣調用該函數：

(find-length 0 (list 2 3 4 3 5 3))

我們評估，該計劃將遞歸調用：

(find-length 1 '(3 4 3 5 3)) 
(find-length 2 '(4 3 5 3)) 
(find-length 3 '(3 5 3)) 
(find-length 4 '(5 3)) 
(find-length 5 '(3)) 
(find-length 6 '()) ; end condition, return 6

This question適用於通用尾遞歸一個很好的參考。

來源

2012-10-10 03:45:29

2尾爲長度[球拍]遞歸函數

回答

相關問題