2.1 递归就是栈处理的
为了理解"递归本来就是栈处理"这一事实, 让我们回到递归的定义本身.
在递归的形式化定义中已经说过, 所有的(能够终止的)递归都必须:
1). 具有基准情形/简单情形,
2). 一组能够将所有情形规约/递推[reduce]至基准情形的规则.
也即, 一般来说, 需要通过递归来处理的事情, 我们的出发点不是“基础情形”, 而是"想要知道现在的情形", 但是"现在的情形"需要"根据规约规则回到基础情形, 然后再根据基础情形知道现在的情形".
如果我们称"情形"为case, 或者称之为状态state/status, 或者称之为情况situation, 我们称"现在想要知道的情形"为wanted case, 称"基础情形"为base case, 那么我们有:
figure 2.1
===============================================================
wanted
case
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
stack base
@@@
@--> middle case i - 1 <<<<<<<<<<<<<<< stack middle 1
@@@@@
@--> middle case i - 2 <<<<<<<<<<<<< stack middle 2
@@@@@@@
@--> ...
@@@@@@@@@
@--> middle case 1 <<<<<<<<<<<<< stack middle i - 1
@@@@@@@@@@@
@--> base case <<<<<<<<<<<<<<< stack top
===============================================================
见figure 2.1. 在C语言中, 你想要知道的情形/状态, 要么是一个变量值, 要么是几个变量值的组合[变量值即变量的状态, 很容易理解吧]. 没错, 这是基本的抽象; 至于你想要基于这个状态/变量值输出什么内容/执行什么动**怎么干怎么干对吧.
figure
2.1描述了, 想要知道wanted case[就是说, wanted case里面的变量值/状态现在是未知的, 在等待确定],
只能不断地向base case推进; 直到你知道了base case, 才能得知wanted case[现在, wanted
case中的变量值确定下来] -- 请请请注意了, 你不是通过base case一下子就知道了wanted case的!过程是这样的:
1. 根据规约规则/递推规则不断往基础情形推进.
wanted case ==> middle case i -1 ==>...==>base case.
2. 根据base case, 往wanted case回溯.
wanted case <== ... <== middle case 1 <== base case.
好的, 让我们来看行进路径:
先从wanted case开始走, 然后我们走到了base case; 此时我们从base case往回走, 直到退回到wanted case. 最后的base case最先回退.
于是, 这和LIFO[Last In First Out, 后进先出]是完全契合的: 最后到达的最先返回/最后进入的最先出来.
在figure
2.1中, 如果我们把wanted case(就是几个变量是吧)放到一个小箱子中, 这个小箱子称之为stack base;
此时箱子中的变量的值/状态还不确定; 然后我们开始在这个箱子之上再放箱子, 这个箱子称之为stack middle 1, 用来把middle
case i - 1的状态装进去... 如是直到我们将base case放到stack top的箱子中; 此时我们知道箱子中的值了;
由于我们的箱子是一个一个叠起来放的; 因此我们只能一次又一次地拿开箱子以确定下面的箱子中的变量的状态; 最后直到最底下的箱子状态确定,
于是我们知道了wanted case. 因此, 最低下的箱子被称之为栈底(stack base), 最顶上的箱子被称为栈顶(stack
top).
如是, 我们非形式化地证明了一个结论; 也就是本小节的主题; 这个主题是:
递归就是栈处理的.
ok, 本小节完毕.
