Линейный рекурсивный и линейный итерационный процесс (LISP)

Question

Итак, я читаю книгу SCIP, которая использует язык Lisp для объяснения основных понятий, и в настоящее время я застрял на разнице между Линейной рекурсивностью и Линейным итеративным процессом.

и пример, используемый для демонстрации различияэто вычисление n!

Линейный рекурсивный процесс

 (if (= n 1)
 1
 (* n (factorial (- n 1))))) 

он производит этот процесс:

(* 6 (factorial 5))

(* 6 ( * 5 (factorial 4)))

(* 6 ( * 5 ( * 4 ( factorial 3))))

(* 6 ( * 5 ( * 4 ( * 3 ( factorial 2)))))

(* 6 ( * 5 ( * 4 ( * 3 (*2 (factorial1))))))

(* 6 ( * 5 ( * 4 ( * 3 (*2 1)))))

(* 6 ( * 5 ( * 4 ( * 3 2))))

(* 6 ( * 5 ( * 4 6)))

(* 6 ( * 5 24))

(* 6 120)

720

Линейный итерационный процесс

(define (factorial n)
 (if (= n 1)
 1
 (* n (factorial (- n 1))))) 

производит следующий процесс

(Factorial 6)

(Fact-tier    1  1  6)

(Fact-tier    1  2  6)

(Fact-tier    2  3  6)

(Fact-tier    6  4  6)

(Fact-tier  24  5  6)

(Fact-tier 120  5  6)

(Fact-tier 720  6  6)

720

Несмотря на то, что я понял основное различие между ними, я все еще не понимаю этот абзац

"Контраст между двумя процессамиможно увидеть по-другому. В итеративном случае программные переменные предоставляют полное описание состояния процесса в любой точке. Если мы остановим вычисления между шагами, все, что нам нужно будет сделать, чтобы возобновить вычисления, это предоставитьинтерпретатор со значениями трех программных переменных. В рекурсивном процессе это не так. В этом случае имеется некоторая дополнительная «скрытая» информация, поддерживаемая интерпретатором и не содержащаяся в переменных программы, которая указывает «где находится процесс». '' при согласовании цепочки отложенных операций. Чем длиннее цепочка, тем больше информацииaintained.

Answer 1

Рекурсивная версия имеет следующую трассировку:

  0: (FACTORIAL 10)
    1: (FACTORIAL 9)
      2: (FACTORIAL 8)
        3: (FACTORIAL 7)
          4: (FACTORIAL 6)
            5: (FACTORIAL 5)
              6: (FACTORIAL 4)
                7: (FACTORIAL 3)
                  8: (FACTORIAL 2)
                    9: (FACTORIAL 1)
                    9: FACTORIAL returned 1
                  8: FACTORIAL returned 2
                7: FACTORIAL returned 6
              6: FACTORIAL returned 24
            5: FACTORIAL returned 120
          4: FACTORIAL returned 720
        3: FACTORIAL returned 5040
      2: FACTORIAL returned 40320
    1: FACTORIAL returned 362880
  0: FACTORIAL returned 3628800

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

«Итеративный» процесс имеет следующую трассировку:

  0: (FACTORIAL 1 1 10)
    1: (FACTORIAL 1 2 10)
      2: (FACTORIAL 2 3 10)
        3: (FACTORIAL 6 4 10)
          4: (FACTORIAL 24 5 10)
            5: (FACTORIAL 120 6 10)
              6: (FACTORIAL 720 7 10)
                7: (FACTORIAL 5040 8 10)
                  8: (FACTORIAL 40320 9 10)
                    9: (FACTORIAL 362880 10 10)
                      10: (FACTORIAL 3628800 11 10)
                      10: FACTORIAL returned 3628800
                    9: FACTORIAL returned 3628800
                  8: FACTORIAL returned 3628800
                7: FACTORIAL returned 3628800
              6: FACTORIAL returned 3628800
            5: FACTORIAL returned 3628800
          4: FACTORIAL returned 3628800
        3: FACTORIAL returned 3628800
      2: FACTORIAL returned 3628800
    1: FACTORIAL returned 3628800
  0: FACTORIAL returned 3628800

В случае итеративного процессаВы можете видеть, что результат всегда один и тот же: промежуточные результаты просто передаются обратно без изменений на верхний уровень. Другими словами, мы уже знаем окончательный результат, когда мы находимся на самом внутреннем вызове. Для любого промежуточного значения не требуется хранения, поскольку все хранится в аргументах функции. Вы также можете изменить аргументы с новыми значениями и циклом.

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

(FACTORIAL 1 1 10)
(FACTORIAL 1 2 10)
(FACTORIAL 2 3 10)
(FACTORIAL 6 4 10)
(FACTORIAL 24 5 10)
(FACTORIAL 120 6 10)
(FACTORIAL 720 7 10)
(FACTORIAL 5040 8 10)
(FACTORIAL 40320 9 10)
(FACTORIAL 362880 10 10)
(FACTORIAL 3628800 11 10)
FACTORIAL returned 3628800

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