Как я могу передать список в качестве параметра функции, рекурсивно добавляющей к нему элементы, и оставить его без изменений, когда он выйдет из рекурсии?
Я хочу использовать список на каждом уровне рекурсии со списком, имеющим значения, добавленные более глубокими уровнями рекурсии.
Чтобы быть более конкретным, я хочу выполнить поиск DFS на графике и сохранить в списке узлы, которые я посетил.
Один из способов сделать это — просто вернуть список, чтобы у вас был доступ к нему на более высоких уровнях рекурсии.
Другой способ - сохранить ваш список в переменной вне рекурсии. Другими словами, не хранится в стеке. Поскольку использовать глобальную переменную для этого не рекомендуется, нам нужна некоторая локальная рекурсия.
Следующий код — глупый способ перевернуть список, но он иллюстрирует технику, о которой я говорю.
(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)
Можете ли вы применить эту технику для своих целей?
Если вы создаете новый список, добавляя значение в старый список, этот старый список не изменяется.
(define old '(1 2 3))
(define new (cons 55 old))
new
>(55 1 2 3)
old
>(1 2 3)
«Хвост» первых минусов в «новых» — это список «старых». Но старый не изменился.
(cdr new)
> (1 2 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.
