使用列表的方式累积递归

Question

如何将列表作为参数传递给函数，以递归方式向其中添加元素，并在递归出来时使其未经修改？

我想在递归的每个级别使用列表，其中列表具有通过更深的递归级别添加的值。

更具体地说，我想在图上做一个DFS搜索，我想在列表中存储我访问过的节点。

Answer 1

这样做的一种方法就是返回列表，以便在更高级别的递归中访问它。

另一种方法是让您的列表存储在递归之外的变量中。换句话说，不存储在堆栈上。由于使用全局变量不是一个好主意，所以我们需要有一些本地递归。

下面的代码是一个愚蠢的方式来扭转列表，但它确实说明了我正在谈论的技术。

(define (letrecreverse lst) 
    (letrec ((retlist '()) 
      (reverse (lambda (lst) 
         (if (null? lst) 
          '() 
          (begin 
          (set! retlist (cons (car lst) retlist)) 
          (reverse (cdr lst))))))) 
    (reverse lst) 
    retlist)) 

(letrecreverse '(1 2 3 4)) 
;outputs '(4 3 2 1) 

您可以采用这种技术用于您的目的吗？

Answer 2

如果通过将值列入旧列表来构建新列表，则该旧列表是未修改的。

(define old '(1 2 3)) 
(define new (cons 55 old)) 

new 
>(55 1 2 3) 
old 
>(1 2 3) 

“new”中第一个cons的'tail'是列表“old”。但老年人没有改变。

(cdr new) 
> (1 2 3) 

Answer 3

如果我明白你的问题正确，这可能是一个解决办法：

;; Just a helper to print the current list. 
(define (show list) 
    (display "list = ") 
    (display list) 
    (newline) 
    (flush-output)) 

;; Maximum depth of recursion 
(define max-recur 5) 
;; Original list is backed-up here. 
(define orig-list null) 

(define (recur list depth) 
    (if (null? orig-list) 
     (set! orig-list list)) 
    (cond ((< depth max-recur) 
     (show list) 
     (recur (cons (random max-recur) list) (add1 depth))) 
     (else orig-list))) 

采样运行：

> (recur '(1) 0) 
list = (1) 
list = (1 1) 
list = (2 1 1) 
list = (3 2 1 1) 
list = (4 3 2 1 1) 
(1) ;; In the end you get the original list back.