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