带列表的方案累积递归 [英] Scheme accumulative recursion with lists

问题描述

如何将列表作为参数传递给以递归方式向其添加元素的函数，并且在递归结束时不对其进行修改?

How can I pass a list as a parameter to a function adding elements to it recursively,and have it unmodified when it comes out of recursion?

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

I want to use the list at each level of recursion with the list having the values added by deeper recursion levels.

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

To be more specific I want to do a DFS search on a graph and I want to store in the list the nodes I visited.

推荐答案

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

One method of doing this is just to return the list so you have access to it at higher levels of recursion.

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

Another method is to have your list be stored in a variable outside of the recursion. In other words not stored on the stack. Since it is not a good idea to use a global variable for this we need to have some local recursion.

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

The following code is a foolish way to reverse a list but it does illustrate the technique I am talking about.

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

你能采用这种技术来达到你的目的吗?

Can you adopt this technique for your purposes?

这篇关于带列表的方案累积递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！