线性递归与线性迭代过程(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

尽管我确实理解了他们之间的主要区别，但我还是不明白这段话

“这两个过程之间的对比可以用另一种方式来看待。在迭代的情况下，程序变量在任何一点上都提供了对流程状态的完整描述。如果我们停止了步骤间的计算，那么我们需要做的就是恢复计算，为解释器提供三个程序变量的值。递归过程则不是这样。在这种情况下，还有一些额外的“隐藏”信息，这些信息由解释器维护，不包含在程序变量中，这表明在协商延迟操作链时进程在哪里。链越长，必须维护的信息就越多。

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

在迭代过程中，您可以看到结果总是相同的:中间结果只是不改变地传递回toplevel。换句话说，当我们处于最内线的时候，我们已经知道了最终的结果。任何中间值都不需要存储，因为所有内容都保存在函数参数中。您也可以使用新的值和循环修改参数。

实际上，这基本上是在对尾位置的调用进行优化时发生的情况:递归调用与调用者重用相同的堆栈框架，并按如下方式扁平跟踪：

(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

最后，您的行为与使用循环构造的行为相同。但是请注意，即使使用循环，您也可以从这个技巧中获益:尾调用消除不仅限于递归调用，还可以在调用函数时安全地重用框架时执行。