回复：C语言递归调用转化为栈处理的一般式, 申请精华.

=========================> Chapter 5 <=========================
将 系统栈 处理转为 ADT栈 处理
也即本文的主题, 将递归调用转化为栈处理
===============================================================
###############################################################

=========================> Chapter 5 <=========================
将 系统栈 处理转为 ADT栈 处理
===============================================================
###############################################################
Section 5.1 为什么尾递归可以直接化为[不需要使用栈的]迭代处理
###############################################################
童鞋们应该还记得, LZ在说明递归形式时曾给出过结论, 尾递归可以直接化解为迭代处理, 不需要使用栈.
下面我们来看看为什么.
本质上, 需要栈处理的原因是因为我们需要保存任意函数计算的中间状态.
让我们把 C语言的函数 这个概念稍微抽象一下先.
让我们把任意 C语言函数记为 foo.
foo的形式自然是
ret foo(paras);
ret代表 foo 函数的返回类型/返回值, paras[parameters]代表 foo 函数的参数序列.
tips:
##############################################
我们知道, 如果不给C语言函数传递指针, 只是调用C语言函数, 那么除了全局变量, 这个函数是没有办法改变这个函数之外的变量的值的.
也即, 只是调用[请注意LZ没有把这个函数的返回值赋值给任意一个变量, 只是, 简单地调用它]:
foo(para1, para2, ...);
如果, 传递给 foo 的参数para1, para2, ... 都不是指针[请注意, C语言中, 当你传递"数组"时, 传递的只是数组首地址, 也即当数组作为形式参数时, 实际上退化为一个指针. 所以LZ这里的"指针", 也包括"数组形式的指针"], 那么foo什么都改变不了 --
除了全局变量 / foo函数内部的静态变量.
[实际上, foo函数内部的静态变量就是只有foo函数能访问的全局变量].
更进一步, 如果我们把foo函数内部的静态变量看成是foo函数自带的东西, 那么除了全局变量之外, foo函数什么都改变不了.
##############################################
我们之前已经说过, 任意变量都可以看作是存储"状态"的东西/盒子.
让我们把 foo函数之外的 所有的变量的状态 称之为 环境状态[Status of Environment],
把 foo函数之内的 foo函数能够操作的变量的状态 称之为 foo局部状态[Status of foo].
那么, 如果只是简单地调用 foo 改变了环境状态[也即, 传递指针给它, foo修改了指针指向的内容, 或者, foo修改了某个全局变量], 我们就称, foo函数具有 副作用[Side Effect].
否则, 我们称 foo函数没有副作用.
tips:
##############################################
函数无副作用不代表它线程安全.
线程安全和有无副作用并不相干,
这种情况主要发生在, foo函数一开始修改了环境状态, 然后返回前又还原环境状态的情形下.
但是, 如果foo函数从不修改环境状态, 并且foo函数不自带静态变量[从而不会修改它], 那么它是线程安全的.
##############################################
printf函数是有副作用的. 因为它改变了输出流. 输入输出流是环境状态.
swap是有副作用的. 因为它交换了两个环境状态.
int add_int(int l, int r)
{
　　return l + r;
}
add_int本身是没有副作用的, 它不会改变环境状态.
然而, 如果写
int ret = add_int(3, 5);
那么"="操作改变了环境状态 ret. 有副作用的操作不是 add_int, 而是"=" -- 修改动作本身.
我们的整个C语言程序, 可以视为环境状态被改变的过程.
于是, 整个程序可以被视为一个操纵环境状态序列的自动状态机.
同理, foo函数 可以被视为操纵 foo局部状态序列的自动状态机.
C语言是依赖函数副作用编程的语言. 大多数命令式范式的语言都是这样的.
累了...
to be continued...

马克一个。之后看。。

LS的很凶残~
N叉树遍历非栈迭代算法我基本没考虑过
表示凶残的孩纸伤不起

太深奥…不过还是要看完

╮(╯▽╰)╭
5.1节我恨...
还是略过Section 5.1吧, 太罗嗦又没有任何实际内容.
...... 可是要是现在才看到这楼是不是晚了点... 是不是有把 5.1看完的...
LZ必须道歉, 你悲剧地忍受了LZ的啰嗦... LZ连自己回头看自己码的这坨... 只想

天啊, LZ真的比唐僧还唐僧啊.
=============================================
PS: 再次澄清尾递归. 任何在返回值上再进行计算的递归都不是尾递归, 因为在返回值上再进行计算就要求栈回退, 要求回退就不是尾递归.
尾递归的形式, 只有一种, 即在函数最后写上:
return foo(...);
就这是尾递归.
=============================================

=========================> Chapter 5 <=========================
将 系统栈 处理转为 手工栈 处理
===============================================================
###############################################################
Section 5.2 模拟
###############################################################
只要是系统栈能处理的东西, 手工栈就能处理[除了速度之外...].
基本的想法就是模拟. 模拟系统栈的保存动作, 模拟函数调用和返回. 递归仍然该怎么写怎么写, 写完了照着模拟就是.
LZ是不是很找抽...
to be continued...

天呐我竟然看完了……

continuation of Section 5.2
先看一个简单的实例, 这个实例将一个十进制的自然数转换为2进制的形式输出.
十进制正整数转为2进制的算法, 以13为例, 每次除以2取余.
/ 2　　　　13　　-- 1　　// LSB lowest bit
/ 2　　　　 6　　-- 0
/ 2　　　　 3　　-- 1
/ 2　　　　 1　　-- 1　　// HSB highest bit
/ 2　　　　 0
即转换的结果是 1101
因为第一次除以2的余数是最低位, 所以应该最后输出.
递归的算法很简单, 每次都除以2, 除以2之前的状态保存在栈帧中, 等待算法结束后输出余数即可. 当商为0时终止.
代码如下所示. dec2bin即转换并输出的函数.


main函数里面有一个值得初学者注意的例子, 当使用scanf时, 如果输入的格式和代码要求的格式不匹配, 那么scanf是不能正确获取输入的. 因此需要清空输入缓冲区和重试的处理. 在循环获取输入的情况下尤其要注意这一点.
在 dec2bin 函数中, LZ加了两个标签, 这两个标签是并不影响执行流, 因为整个函数中根本就没有goto语句. 这两个标签是后面为了说明加的.

坑了吗..

牛！！！

marj