recursion - 使用列表计划累积递归

Question

如何将列表作为参数传递给以递归方式向其添加元素的函数，并在递归结束时保持不变？

我想在每个递归级别使用列表，该列表具有由更深的递归级别添加的值。

更具体地说，我想在图表上进行 DFS 搜索，并且我想将访问过的节点存储在列表中。

Answer 1

如果您通过将值添加到旧列表来构建新列表，则该旧列表不会被修改。

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

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

“新”中第一个缺点的“尾巴”是“旧”列表。但旧的并没有改变。

(cdr new)
> (1 2 3)

Answer 2

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

另一种方法是将列表存储在递归之外的变量中。换句话说，不存储在堆栈上。由于为此使用全局变量不是一个好主意，因此我们需要进行一些局部递归。

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

(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 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.