Scheme中的遞歸函數

Question

我需要製作一個遞歸函數，該函數需要一個對象和一個向量，並返回在我的對象參數之前的所有對象的列表。

我把它用迭代這樣做的：

(define (precedes obj vec) 
    (do ((i 1 (+ i 1)) 
     (list '() (if (eqv? obj (vector-ref vec i)) 
      (cons(vector-ref vec (- i 1)) list) 
      list))) 
    ((= i (vector-length vec)) list)) 
) 

但我有很多的麻煩試圖找出如何使用遞歸做同樣的事情。我很困惑，我如何通過遞歸調用來繼續增加矢量。到目前爲止，我已經是這樣的：

(define (precedes2 obj vec) 
    (define list '()) 
    (if (eqv? obj (vector-ref vec i)) 
     (cons(vector-ref vec(- i 1)) list) 
     list))) 

我想我會用我的if語句名詞前用同樣的邏輯，但我不知道現在該怎麼用更新的調用同一個函數向量。任何幫助都會很棒。

Answer 1

您處於從迭代實現轉爲遞歸的有趣位置;通常人們走向另一個方向。幸運的是，從做循環到遞歸非常簡單。在一般情況下，一個做循環可以被重寫如下：

(do ((i i-init i-step) 
    (j j-init j-step) 
    ...) 
    (test result) 
    body) 

成爲

(define f (i j ...) 
    (cond 
    (test result) 
    (else body (f i-step j-step ...)))) 

(f i-init j-init ...) 

，翻譯是使用名爲讓利通常寫，但：

(let f ((i i-init) 
     (j j-init) 
     ...) 
    (cond 
    (test result) 
    (else body (f i-step j-step ...)))) 

所以（我還沒有測試過這個代碼）你原來的功能

(define (precedes obj vec) 
    (do ((i 1 (+ i 1)) 
     (list '() (if (eqv? obj (vector-ref vec i)) 
      (cons(vector-ref vec (- i 1)) list) 
      list))) 
    ((= i (vector-length vec)) list)) 
) 

會變成

(define (precedes obj vec) 
    (let loop ((i 1) 
      (list '())) 
    (cond 
     ((= i (vector-length vec)) list) 
     (else (loop (+ i 1) 
        (if (eqv? obj (vector-ref vec i)) 
         (cons (vector-ref vec (- i 1)) list) 
         list))))))