Scheme accumulative recursion with lists

Question

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.

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.

Answer 1

If you build a new list by consing a value onto an old list, that old list is unmodified.

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

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

The 'tail' of the first cons in "new" is the list "old". But old hasn't changed.

(cdr new)
> (1 2 3)

Answer 2

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?

Answer 3

If I understood your question correctly, this could be one solution:

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

Sample run:

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