Схема накопительной рекурсии со списками - PullRequest
Новая
       42

Схема накопительной рекурсии со списками

1 голос
/ 05 мая 2010

Как я могу передать список в качестве параметра функции, добавив в нее элементы рекурсивно, и сделать ее неизменной, когда она выйдет из рекурсии?

Я хочу использовать список на каждом уровне рекурсии со списком, имеющим значения, добавленные более глубокими уровнями рекурсии.

Чтобы быть более точным, я хочу выполнить поиск в DFS на графике и сохранить в списке посещенные мной узлы.

Ответы [ 3 ]

1 голос
/ 05 мая 2010

Один из способов сделать это - просто вернуть список, чтобы иметь доступ к нему на более высоких уровнях рекурсии.

Другой способ - сохранить ваш список в переменной вне рекурсии. Другими словами, не хранятся в стеке. Поскольку для этого не рекомендуется использовать глобальную переменную, нам нужна локальная рекурсия.

Следующий код - глупый способ перевернуть список, но он иллюстрирует технику, о которой я говорю. 

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

Можете ли вы принять эту технику для своих целей?

1 голос
/ 05 мая 2010

Если вы строите новый список, помещая значение в старый список, этот старый список не изменяется. 

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

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

«Хвостом» первых минусов в «новом» является список «старых». Но старое не изменилось. 

(cdr new)
> (1 2 3)
0 голосов
/ 06 мая 2010

Если я правильно понял ваш вопрос, это может быть одним из решений: 

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