0

我正在阅读《计算机编程的概念、技术和模型》，开头有一段代码，无论我多么努力，我都无法理解。

declare Pascal AddList ShiftLeft ShiftRight

fun {Pascal N}
   if N==1 then [1]
   else
      L in
      L = {Pascal N-1} % Recursion
      {AddList {ShiftLeft  L}
               {ShiftRight L}}
   end
end

fun {ShiftLeft L}
   case L of H|T then
      H|{ShiftLeft T}  % Recursion
   else [0]
   end
end

fun {ShiftRight L}
   0 | L
end

fun {AddList L1 L2}
   case L1 of H1|T1 then
      case L2 of H2|T2
      then
     H1+H2|{AddList T1 T2} % Recursion
      end
   else nil
   end
end

我有点了解语言结构（这是对它的介绍），但真正阻碍我的是递归。

我试图在每个递归调用上贴一个标签，抽象地说明这里发生了什么，但我就是想不通。

我要求的是对这些功能如何工作的清晰而简单的解释。

4

2 回答 2

0

从 N == 1 开始：这很简单。结果只是[1]。

现在检查 N == 2：

First we calculate L = {Pascal N-1} = {Pascal 2-1} = {Pascal 1} = [1]
Now shifted to the left: [1 0]
Shifted to the right: [0 1]
AddList just adds elementwise. So the result for {Pascal 2} is [1 1].

现在对于 N == 3：

{Pascal 2} = [1 1]
Shifted left:  [1 1 0]
Shifted right: [0 1 1]
Added:         [1 2 1]

当然，该程序以相反的方式工作：它从一些较大的N. 但在Pascal函数开始时，程序会反复递归，直到参数N变为1。像这样的东西：

{Pascal 3}
   {Pascal 2}
      {Pascal 1}
      [1]
   [1 1]
[1 2 1]

编辑：程序中实际上有多种递归。第一个Pascal以某个整数开头N并递归到1.

另一个（在辅助方法中）从一个由头和尾组成的列表开始，一旦列表为空就停止，即不能再拆分。（这是使用所谓的 cons 列表，一种本质上递归的数据类型。）

于 2013-03-06T16:52:05.473 回答
0

wmeyer 的解释非常好。我只想添加一个可能有用的“可视化”-->

首先，我用的是书的原版（PDF），我相信，功能是这样的 -->

declare Pascal AddList ShiftLeft ShiftRight
fun {Pascal N}
   if N==1 then [1]
   else
      {AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}}
   end
end

fun {ShiftLeft L}
   case L of H|T then
      H|{ShiftLeft T}
   else [0] end
end

fun {ShiftRight L} 0|L end

fun {AddList L1 L2}
   case L1 of H1|T1 then
      case L2 of H2|T2 then
         H1+H2|{AddList T1 T2}
      end
   else nil end
end

想象一下，您想查看帕斯卡三角形的第八行。你要输入：

{Browse {Pascal 8}}

即，您想显示将 8 馈送到本书/此处定义的函数 Pascal 的结果。

首先，函数测试它刚刚传递的值是否为 1（直到递归的最后一次迭代（或最终的递归调用）才会为真，此时 [1]（来自 if N= =1) 将作为 THAT CALL OF Pascal 的输出返回，并将（Pascal 的）执行“链”传递回最先调用的下一个最近的调用（该结果 [1] 被添加到匹配的 ShiftLeft 或 ShiftRight，然后该结果被发送回链上，一直循环，直到它到达第一个（Pascal 8）。所以调用深入 8 个级别，然后将答案传递回这些级别，直到你得到了最终的答案......但我已经跳到前面了。

好的，由于您输入了 8，因此测试 N==1 失败，因此无法立即移动“列表”并将它们添加到 else 子句中，该函数无法使用未定义的术语执行此操作在'方程式'中说“我会尝试 N - 1！也许这将是最终答案！” （对于 ShiftLeft 和 ShiftRight - 所以每次递归发生时都会发生这种分支）

因此，该函数在 ShiftLeft 和 ShiftRight 中等待来自 Pascal N-1 的答案......等待，等待......

好吧，对于 N==1，{Pascal 7} 也不是真的，所以 Pascal 的新调用（“调用”，第二和第三调用，左右！）也会问“什么是 Pascal N - 1 “（这次是7-1）他们都会等待答案......

这种情况一直在继续……哦，等等，直到 N==1！

然后 [1]，一个列表，被返回 BACK UP THE CHAIN ......所以，每个连续的等待函数调用，最近的第一个（请记住，所有这些都在向下到达“底部”的过程中越来越多地发生其中 N==1 随着拆分的增加（通过每次调用一次调用 ShiftLeft 和 ShiftRight））最终可以使用它一直在等待的答案进行 AddList 计算，该答案来自它自己对 ShiftLeft 和 ShiftRight 的个人、私人调用。

一切都一直到底部，分解成越来越多的函数调用，然后我们回到顶部，最后可以得到一个返回的答案。最后的答案是第一次调用 Pascal 函数 {Pascal 8} 的 else 子句，现在，在内部，（因为 Pascal 三角形的第 8 行是 [1 7 21 35 35 21 7 1]）将如下所示：

{AddList [1 7 21 35 35 21 7 0] [0 7 21 35 35 21 7 1]} <-- 至少我认为这是要添加的最终列表的样子

添加后的列表作为最终答案返回并显示：[1 7 21 35 35 21 7 1]

于 2019-06-30T23:31:26.543 回答