Понимание хвостовой рекурсии 2

Question

Первоначально я опубликовал один вопрос " понимание хвостового рекурсивного ответа вектора -> списка", и это дополнительные вопросы. мое общее понимание схемы действительно расплывчато. поэтому у меня теперь есть еще несколько вопросов:

;;;;;; original code ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define vector->list:rec
 (lambda (v)
  (letrec ((helper
      (lambda (vec r i)
        (if (< i 0) 
            r
            (helper vec (cons (vector-ref v i) r) (- i 1))  ;; Q1
            ))))
    (if (> (vector-length v) 0)  ;; line 9
      (helper v                  ;; line 10 
              (cons (vector-ref v (- (vector-length v) 1)) '()) 
              (- (vector-length v) 2))
      '()))))

Q2) рекурсия хвоста, которая делает меня действительно трудным для понимания. Я понял, почему им нужна хвостовая рекурсия, и в основном они используют ее, чтобы избежать итерации, поэтому они используют хелпер в качестве промежуточной подпрограммы... чтобы они могли избежать помещения каждой итерации в стек... как-то так. и выражение letrec/ лямбда, как здесь:

;;;;;;;;;letrec/lambda express;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (some-procedure...)
  (letrec ((helper (lambda (x) 
               ...
               (if some-test?
                   (helper ...))))) ; recursive call --- Q2-1
       ...
    (helper ...)  ; call to recursive local procedure  ---- Q2-2
  ...))

строка Q2-2: почему это "локальная рекурсия"? "местный" звучит для меня рекурсивно для промежуточной рутины... здесь промежуточная означает, что мое понимание..

[моя путаница] хвостовая рекурсия не должна повторяться (вызывать) сама по себе до конца всей программы - так что не должно быть в промежуточной подпрограмме.. = не должно быть внутри помощника? исходя из моего понимания до сих пор... хелпер предназначен для промежуточной подпрограммы, которая заключена в выражение letrec..?.), поэтому вызывает только себя в конце (мое значение..: вне letrec..?).

Answer 1

Прежде всего, я бы немного переписал вам пример к этому:

(define (vector->list-iter v)  
  (let loop ((i (- (vector-length v) 1)) (acc '()))
    (if (< i 0)
        acc
        (loop (- i 1) (cons (vector-ref v i) acc)))))

И чтобы увидеть разницу, давайте сделаем нерекурсивную версию:

(define (vector->list-rec v)
  (define len (vector-length v))
  (let loop ((i 0))
    (if (>= i len)
        '()
        (cons (vector-ref v i) (loop (+ i 1))))))

В Схеме нет функциональности цикла. Только рекурсия и рекурсия не увеличивают стек, потому что на предыдущем шаге есть еще что-то, что называется хвостовой рекурсией.

Так как мы можем перебирать вектор любым способом (это O(1) доступ), мы можем перебирать его с последнего до первого или с первого до последнего. Поскольку список может быть составлен только последним, нерекурсивная версия не применяется cons на первый элемент, пока он не составил весь список, кроме первого элемента. Это делает вектор из 5 элементов иметь 5 продолжений при попадании в базовый вариант. Если бы это был большой вектор, это может привести к переполнению стека.

В первом примере сначала создается список, состоящий из последнего элемента, а когда это делается, он возвращается. Не нужно ничего противодействовать, так как согласование было сделано до рекурсии. Не каждая проблема может быть решена таким образом. Представьте, что вы хотите скопировать список. Это может быть повторено от начала до конца, но построено от конца до начала. Без мутации или лишних последствий невозможно сделать такую ​​процедуру рекурсивной.