c语言吧 关注：801,793贴子：4,376,559
不感兴趣
开通SVIP免广告
=========================> 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...
将 系统栈 处理转为 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...
不感兴趣
开通SVIP免广告
╮(╯▽╰)╭
5.1节我恨...
还是略过Section 5.1吧, 太罗嗦又没有任何实际内容.
...... 可是要是现在才看到这楼是不是晚了点... 是不是有把 5.1看完的...
LZ必须道歉, 你悲剧地忍受了LZ的啰嗦... LZ连自己回头看自己码的这坨... 只想
天啊, LZ真的比唐僧还唐僧啊.
=============================================
PS: 再次澄清尾递归. 任何在返回值上再进行计算的递归都不是尾递归, 因为在返回值上再进行计算就要求栈回退, 要求回退就不是尾递归.
尾递归的形式, 只有一种, 即在函数最后写上:
return foo(...);
就这是尾递归.
=============================================
=========================> Chapter 5 <=========================
将 系统栈 处理转为 手工栈 处理
===============================================================
###############################################################
Section 5.2 模拟
###############################################################
只要是系统栈能处理的东西, 手工栈就能处理[除了速度之外...].
基本的想法就是模拟. 模拟系统栈的保存动作, 模拟函数调用和返回. 递归仍然该怎么写怎么写, 写完了照着模拟就是.
LZ是不是很找抽...
to be continued...
将 系统栈 处理转为 手工栈 处理
===============================================================
###############################################################
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语句. 这两个标签是后面为了说明加的.
.......
被吞了... 我艹.
难道是因为我一年多没填坑的原因吗?......
这帖子坑了这么久, ... 实在是 LZ 越来越懒, 俗务缠身...
终于还是决定把这个坑马马虎虎填了吧...
-------------------
就不再说别的了, 直接上例子... 看了这个例子, 就会明白的, 其实就是简单的模拟...
用汉诺塔来说明吧...
#include <stdio.h>
void hanoi(char from, char pass, char to, int n)
{
____if (n == 1) {
________printf("%c ==> %c\n", from, to);
____} else {
________hanoi(from, to, pass, n - 1);
________hanoi(from, pass, to, 1);
________hanoi(pass, from, to, n - 1);
____}
}
int main(void)
{
____int n;
____printf("pls input n: ");
____scanf("%d", &n);
____hanoi('A', 'B', 'C', n);
____return 0;
}
这个树形递归的调用栈帧/活动记录状态如下所示:
3 A B C 表示 n = 3, from = A, pass = B, to = C,
然后, 该函数递归调用自己, 调用时传递参数, 所以第一个被调用的函数其
局部变量的值为 n = 2, from = A, pass = C, to = B,
...
______________________n, from, pass, to
__________________________3 A B C
______________________/______|______\
____________2 A C B________1 A B C ________2 B A C
___________/___|___\________A==>C_________/___|___\
__________/____|____\____________________/____|____\
____1 A B C__1 A C B__1 C A B______1 B C A__1 B A C__1 A B C
_____A==>C___A==>B___C==>B___________B==>A___B==>C____A==>C
关于这个递归函数的执行路径, 和fibonacci递归是类似的,
请参照前面的 fibonacci递归的图...
被吞了... 我艹.
难道是因为我一年多没填坑的原因吗?......
这帖子坑了这么久, ... 实在是 LZ 越来越懒, 俗务缠身...
终于还是决定把这个坑马马虎虎填了吧...
-------------------
就不再说别的了, 直接上例子... 看了这个例子, 就会明白的, 其实就是简单的模拟...
用汉诺塔来说明吧...
#include <stdio.h>
void hanoi(char from, char pass, char to, int n)
{
____if (n == 1) {
________printf("%c ==> %c\n", from, to);
____} else {
________hanoi(from, to, pass, n - 1);
________hanoi(from, pass, to, 1);
________hanoi(pass, from, to, n - 1);
____}
}
int main(void)
{
____int n;
____printf("pls input n: ");
____scanf("%d", &n);
____hanoi('A', 'B', 'C', n);
____return 0;
}
这个树形递归的调用栈帧/活动记录状态如下所示:
3 A B C 表示 n = 3, from = A, pass = B, to = C,
然后, 该函数递归调用自己, 调用时传递参数, 所以第一个被调用的函数其
局部变量的值为 n = 2, from = A, pass = C, to = B,
...
______________________n, from, pass, to
__________________________3 A B C
______________________/______|______\
____________2 A C B________1 A B C ________2 B A C
___________/___|___\________A==>C_________/___|___\
__________/____|____\____________________/____|____\
____1 A B C__1 A C B__1 C A B______1 B C A__1 B A C__1 A B C
_____A==>C___A==>B___C==>B___________B==>A___B==>C____A==>C
关于这个递归函数的执行路径, 和fibonacci递归是类似的,
请参照前面的 fibonacci递归的图...
看一下这个递归.
整个函数里面的局部变量只有 4 个, 就是 from, pass, to, n.
因此我们可以使用一个结构体来记录这四个变量值:
struct data_t {
____char from;
____char pass;
____char to;
____int n;
};
void hanoi(char from, char pass, char to, int n)
{
____if (n == 1) {
________printf("%c ==> %c\n", from, to);
____} else {
________// 这里调用函数, 意味着:
________// 1. 当前函数的状态(所有局部变量的值)需要保存, 以便从被调用函数返回后,
________// 当前函数的状态(所有局部变量的值)恢复到调用前的状态.
________// 2. 给被调用的函数传递参数, 然后转去被调用函数方执行.
________// 3. 当被调用函数返回, 由于我们在这里调用, 所以返回后从标签 ret_addr1: 处
________// 继续执行剩下的代码.
________hanoi(from, to, pass, n - 1);
// ret_addr1:
________// 同理, 只是被调用函数返回后, 从 ret_addr2: 处继续执行.
________hanoi(from, pass, to, 1);
// ret_addr2:
________// 同理, 被调用函数返回后, 从 ret_addr3: 处继续执行.
________hanoi(pass, from, to, n - 1);
// ret_addr3:
____}
// 这里实际上有个隐式的 return;
}
嗯, 当调用函数时, 我们将调用时调用方的状态全部记录下来, 另外, 我们也记录下"返回地址", 以便从被调用方返回后, 知道返回到调用方的哪个 point / addr 继续执行.
因此, 我们设计如下的数据结构:
typedef enum {
____RET_ADDR1,
____RET_ADDR2,
____RET_ADDR3
} ret_addr;
struct data_t {
____char from; // 保存调用方的 from
____char pass; // .............pass
____char to; // ...............to
____int n; // .................n
____ret_addr addr; // 保存调用方的 "返回地址"
};
okay, 准备工作完成, 接下来我们应该怎么做呢?
整个函数里面的局部变量只有 4 个, 就是 from, pass, to, n.
因此我们可以使用一个结构体来记录这四个变量值:
struct data_t {
____char from;
____char pass;
____char to;
____int n;
};
void hanoi(char from, char pass, char to, int n)
{
____if (n == 1) {
________printf("%c ==> %c\n", from, to);
____} else {
________// 这里调用函数, 意味着:
________// 1. 当前函数的状态(所有局部变量的值)需要保存, 以便从被调用函数返回后,
________// 当前函数的状态(所有局部变量的值)恢复到调用前的状态.
________// 2. 给被调用的函数传递参数, 然后转去被调用函数方执行.
________// 3. 当被调用函数返回, 由于我们在这里调用, 所以返回后从标签 ret_addr1: 处
________// 继续执行剩下的代码.
________hanoi(from, to, pass, n - 1);
// ret_addr1:
________// 同理, 只是被调用函数返回后, 从 ret_addr2: 处继续执行.
________hanoi(from, pass, to, 1);
// ret_addr2:
________// 同理, 被调用函数返回后, 从 ret_addr3: 处继续执行.
________hanoi(pass, from, to, n - 1);
// ret_addr3:
____}
// 这里实际上有个隐式的 return;
}
嗯, 当调用函数时, 我们将调用时调用方的状态全部记录下来, 另外, 我们也记录下"返回地址", 以便从被调用方返回后, 知道返回到调用方的哪个 point / addr 继续执行.
因此, 我们设计如下的数据结构:
typedef enum {
____RET_ADDR1,
____RET_ADDR2,
____RET_ADDR3
} ret_addr;
struct data_t {
____char from; // 保存调用方的 from
____char pass; // .............pass
____char to; // ...............to
____int n; // .................n
____ret_addr addr; // 保存调用方的 "返回地址"
};
okay, 准备工作完成, 接下来我们应该怎么做呢?
下面是完整的模拟代码. 是完全的最笨的那种模拟. 任何递归都可以用这种模拟的办法
来完成转换. 当然, 在这种基本模拟的方式上, 有更好的做法, 就可以采用更聪明的办法.
//--------------------------------------------
#include <stdio.h>
#include <stack.h> // 自己实现一个吧...
// "返回地址"
typedef enum {
____RET_ADDR1,
____RET_ADDR2,
____RET_ADDR3
} ret_addr;
// 用来保存调用方的函数所有状态
struct data_t {
____char from;
____char pass;
____char to;
____int n;
____ret_ddr addr;
};
void set_data(struct data_t *data, char from, char pass, char to, int n, int addr)
{
____data->from = from, data->pass = pass, data->to = to, data->n = n,
____data->addr = addr;
}
void hanoi(char from, char pass, char to, int n)
{
____// 创建一个栈, 每个栈上元素的大小为 sizeof(struct data_t)
____stack_t *st = stack_create(sizeof(struct data_t), NULL);
____struct data_t data;
____char tmp;
// start 就是函数的开始咯.
start:
____if (n == 1) {
________printf("%c ==> %c\n", from, to);
____} else {
________// 保存当前函数的状态(包括所有局部变量, 以及"返回地址")
________set_data(&data, from, pass, to, n, RET_ADDR1);
________stack_push(st, &data);
________// 然后给函数传递参数, 并"调用函数"
________// 这几个赋值就相当于传递参数, goto start 就是"调用函数"
________// ret_addr1 标签就是调用函数完了之后的"返回地址"
________// from = from;
________tmp = pass, pass = to, to = tmp, n = n - 1;
________goto start;
ret_addr1:
________// 同上...
________set_data(&data, from, pass, to, n, RET_ADDR2);
________stack_push(st, &data);
________// from = from, pass = pass, to = to;
________n = 1;
________goto start;
ret_addr2:
________// 同上...
________set_data(&data, from, pass, to, n, RET_ADDR3);
________stack_push(st, &data);
________// to = to;
________tmp = from, from = pass, pass = tmp, n = n - 1;
________goto start;
ret_addr3:
________; // 这里有个分号, C语言不允许标签后面没有语句, 所以用个空语句占位.
____}
// 这里就是原来的递归函数的 return 的地方. return 的时候就回到调用方咯
// 如果栈空了, goto exit 即退出.
____if (stack_isempty(st))
________goto exit;
// 弹栈, 弹出调用方的数据(就是说这里是被调用方执行完了, 要返回到调用方继续)
____stack_pop(st, &data);
// 恢复调用方的数据
____from = data.from, pass = data.pass, to = data.to, n = data.n;
// 调用方在哪里调的, 就返回到那个调用处的下面.
____switch (data.addr)
____{
________case RET_ADDR1:
____________goto ret_addr1;
________case RET_ADDR2:
____________goto ret_addr2;
________case RET_ADDR3:
____________goto ret_addr3;
____}
exit:
____// 销毁手工栈.
____stack_destroy(st);
}
int main(void)
{
____int n;
____printf("pls input n: ");
____scanf("%d", &n);
____hanoi('A', 'B', 'C', n);
____return 0;
}
好了. 以上的代码就是模拟的实例... 看懂这个, 别的递归灵活处理即可.
来完成转换. 当然, 在这种基本模拟的方式上, 有更好的做法, 就可以采用更聪明的办法.
//--------------------------------------------
#include <stdio.h>
#include <stack.h> // 自己实现一个吧...
// "返回地址"
typedef enum {
____RET_ADDR1,
____RET_ADDR2,
____RET_ADDR3
} ret_addr;
// 用来保存调用方的函数所有状态
struct data_t {
____char from;
____char pass;
____char to;
____int n;
____ret_ddr addr;
};
void set_data(struct data_t *data, char from, char pass, char to, int n, int addr)
{
____data->from = from, data->pass = pass, data->to = to, data->n = n,
____data->addr = addr;
}
void hanoi(char from, char pass, char to, int n)
{
____// 创建一个栈, 每个栈上元素的大小为 sizeof(struct data_t)
____stack_t *st = stack_create(sizeof(struct data_t), NULL);
____struct data_t data;
____char tmp;
// start 就是函数的开始咯.
start:
____if (n == 1) {
________printf("%c ==> %c\n", from, to);
____} else {
________// 保存当前函数的状态(包括所有局部变量, 以及"返回地址")
________set_data(&data, from, pass, to, n, RET_ADDR1);
________stack_push(st, &data);
________// 然后给函数传递参数, 并"调用函数"
________// 这几个赋值就相当于传递参数, goto start 就是"调用函数"
________// ret_addr1 标签就是调用函数完了之后的"返回地址"
________// from = from;
________tmp = pass, pass = to, to = tmp, n = n - 1;
________goto start;
ret_addr1:
________// 同上...
________set_data(&data, from, pass, to, n, RET_ADDR2);
________stack_push(st, &data);
________// from = from, pass = pass, to = to;
________n = 1;
________goto start;
ret_addr2:
________// 同上...
________set_data(&data, from, pass, to, n, RET_ADDR3);
________stack_push(st, &data);
________// to = to;
________tmp = from, from = pass, pass = tmp, n = n - 1;
________goto start;
ret_addr3:
________; // 这里有个分号, C语言不允许标签后面没有语句, 所以用个空语句占位.
____}
// 这里就是原来的递归函数的 return 的地方. return 的时候就回到调用方咯
// 如果栈空了, goto exit 即退出.
____if (stack_isempty(st))
________goto exit;
// 弹栈, 弹出调用方的数据(就是说这里是被调用方执行完了, 要返回到调用方继续)
____stack_pop(st, &data);
// 恢复调用方的数据
____from = data.from, pass = data.pass, to = data.to, n = data.n;
// 调用方在哪里调的, 就返回到那个调用处的下面.
____switch (data.addr)
____{
________case RET_ADDR1:
____________goto ret_addr1;
________case RET_ADDR2:
____________goto ret_addr2;
________case RET_ADDR3:
____________goto ret_addr3;
____}
exit:
____// 销毁手工栈.
____stack_destroy(st);
}
int main(void)
{
____int n;
____printf("pls input n: ");
____scanf("%d", &n);
____hanoi('A', 'B', 'C', n);
____return 0;
}
好了. 以上的代码就是模拟的实例... 看懂这个, 别的递归灵活处理即可.
不感兴趣
开通SVIP免广告
