Стиль продолжения прохождения делает хвост рекурсивным?

Question

Больно спрашивать об этом здесь. Это действительно так. Каждый раз, когда я тщетно искал ответы на мои проблемы, я вижу это. Осторожно. Stack Overflow.

В любом случае, какое-то адское влияние заставило меня попытаться решить Башни Ханоя. Мое первое решение было неполным, так как это привело к memory error, если работать слишком много дисков:

(define hanoi 
    (lambda (n from to other) 
    (cond ((< n 0) 
     (error `(Error! Number of disks ,n cannot be less than 0!))) 
     ((= n 0) 
     '()) 
     (else 
     (append (hanoi (- n 1) 
       from 
       other 
       to) 
      `((,from ,to)) 
      (hanoi (- n 1) 
       other 
       to 
       from)))))) 

Я где-то читал, что продолжение-прохождение стиль позволит решить эту проблему. Тем не менее, это didn't help either:

(define hanoi_cps 
    (lambda (n from to other c) 
    (cond ((< n 0) 
     (error `(Error! Number of disks ,n cannot be less than 0!))) 
     ((= n 0) 
     (c '())) 
     (else 
     (hanoi_cps (- n 1) 
       from 
       other 
       to 
       (lambda (x) 
      ((lambda (w) 
       (w `((,from ,to)))) 
      (lambda (y) 
       (hanoi_cps (- n 1) 
         other 
         to 
         from 
         (lambda (z) 
        (c (append x y z)))))))))))) 

Answer 1

В продолжении прохождении стиля, а не расширения пространства стека с помощью рекурсивных вызовов, вы создаете рекурсивно-определенные lambdas в среде, в которых выполняются ваши продолжения ... другими словами, память где-то где-то вдоль линии. Например, с помощью простого факторного алгоритма, то, как правило, написать что-то вроде:

(define (factorial x) 
    (cond ((eq? x 0) 1)) 
      ((eq? x 1) 1)) 
      (else (* x (factorial (- x 1)))))) 

С помощью этого рекурсивного определения для factorial, стек пространство будет использоваться до держать аргументы отсроченной операцию умножения включившей в каждый вызов рекурсивной функции. Продолжение обходя версии одной и той же функции будет выглядеть следующим образом:

(define (factorial x cont) 
    (cond ((eq? x 0) (cont 1)) 
      ((eq? x 1) (cont 1)) 
      (else (factorial (- x 1) (lambda (y) (cont (* x y))))))) 

Что бы потребляли стек-пространство, прежде чем теперь израсходован в среде анонимного лямбда. Среда лямбда в этом случае заполняется значениями, необходимыми для разрешения значения x и cont с каждым рекурсивным вызовом до factorial. Так как cont сам по себе является лямбдой с окружающей средой, вы можете видеть, как память будет в конечном итоге потребляться, поскольку каждое продолжение лямбда должно будет хранить в своей среде лямбду от предыдущего вызова факториалу ... это создает рекурсивно определенное лямбда-продолжение который имеет среду, которая в основном представляет собой рекурсивный список всех продолжений, которые были начислены, хотя рекурсивные вызовы factorial.

Один из способов взглянуть на стиль продолжения прохождения заключается в том, что, в то время как вы в основном преобразуете механизм вызова функций в хвостовой рекурсивный метод, фактические определения самих продолжений являются рекурсивными по своей природе, поэтому вы не действительно устраняя рекурсивную природу алгоритма per se ... другими словами, оценка продолжения, созданного по хвостовым рекурсивным вызовам, требует оценки рекурсивно определенного продолжения внутри него, который сам имеет другое рекурсивно определенное продолжение внутри него и т. д. Среда для продолжения лямбда в конечном итоге выглядит как список из списка-списка и т. Д. Для хранения всех этих рекурсивных определений в среде продолжения лямбда требуется память, так что независимо от того, являетесь ли вы занимая пространство в стеке через обычное рекурсивное соглашение о вызове или потребляя пространство памяти, сохраняя рекурсивно определенные средах в каждом продолжении лямбда, так или иначе вы в конечном итоге выйдете из космоса.

Answer 2

КПС не поможет сделать вещи более эффективно использует память, так как, выполняя его, вы просто заменить кадры стека с анонимными функциями. Если вы хотите, чтобы ваша программа использовала меньше памяти, попробуйте выполнить поиск в обратном направлении (но обратите внимание, что вы должны быть осторожны, чтобы избежать бесконечных последовательностей перемещения).