c语言吧 关注：801,795贴子：4,376,552
不感兴趣
开通SVIP免广告
LZ必须要重申, 因为许多人还在问LZ为什么要化解什么的.
LZ本文的真正价值倒不一定就是化解递归的一般式, 而是让各位C语言和数据结构的初学者深刻地理解C语言的递归. 因为C语言的递归和LZ要讲的东西之间关系太紧密太紧密, 以致于, 如果你不理解LZ所讲的东西, 你未必就能够理解C语言的递归. LZ是在阐述递归本身, 而不是在阐述一种化解方式.
其实LZ想要说的只是:你真的理解C语言的递归了么???真的么? 如果你有自信回答说是, 那么恭喜你, LZ这文章你不用看了. 可惜的是, 如果你说你理解了递归, 但是LZ让你把汉诺塔转换为"非递归形式"时, 你却不会转换, 那么LZ显然有理由认为你可以读读LZ这篇文章, 因为在LZ看来, 要把汉诺塔转换为"非递归形式"太简单了.
LZ本文的真正价值倒不一定就是化解递归的一般式, 而是让各位C语言和数据结构的初学者深刻地理解C语言的递归. 因为C语言的递归和LZ要讲的东西之间关系太紧密太紧密, 以致于, 如果你不理解LZ所讲的东西, 你未必就能够理解C语言的递归. LZ是在阐述递归本身, 而不是在阐述一种化解方式.
其实LZ想要说的只是:你真的理解C语言的递归了么???真的么? 如果你有自信回答说是, 那么恭喜你, LZ这文章你不用看了. 可惜的是, 如果你说你理解了递归, 但是LZ让你把汉诺塔转换为"非递归形式"时, 你却不会转换, 那么LZ显然有理由认为你可以读读LZ这篇文章, 因为在LZ看来, 要把汉诺塔转换为"非递归形式"太简单了.
不感兴趣
开通SVIP免广告
ok.
在阐述运行时刻环境之进程栈之前, LZ想要先提下, 什么是栈(Stack).
1. 栈的广义的, 唯一的涵义, 即, 其概念的内涵, 只有一个： LIFO, Last In First Out, 后进先出. 所有的能够称之为"栈"的东西, 都是这个概念内涵的外延, 或者说, 是这个抽象概念的实例.
2. 进程栈/线程栈正是栈的实例. 为什么将它们称之为栈, 是因为它们是栈的实例.
3. 我们要实现的ADT栈也是栈的实例. 为什么将这个数据结构称之为栈, 也是因为这个数据结构是栈的实例.
那么自然, 进程栈能够处理的事情, ADT栈一样可以处理.
所以LZ标题说的
“把递归化解为栈处理”
它的实际涵义是这样的：
1). 递归本来就是栈处理的. 这里的"栈"是广义的栈.
2). 所谓的化解是指, 因为进程栈的空间有限, 为了防止进程栈空间溢出而导致程序dump, 将其转化为ADT栈处理. 因为ADT栈一般在堆(Heap)上管理内存, 而堆相对来说"内存空间是够用的".
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, 本小节完毕.
为了理解"递归本来就是栈处理"这一事实, 让我们回到递归的定义本身.
在递归的形式化定义中已经说过, 所有的(能够终止的)递归都必须:
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, 本小节完毕.
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, 本小节完毕.
为了理解"递归本来就是栈处理"这一事实, 让我们回到递归的定义本身.
在递归的形式化定义中已经说过, 所有的(能够终止的)递归都必须:
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, 本小节完毕.
不感兴趣
开通SVIP免广告
