递归与goto<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
written by leezy_2000
记得刚开始学习C时,老师和教材都有明训:“千万不要乱用goto语句,否则将导致程序可读性极度下降。但能够极大提高效率地情况,可以考虑使用。”抱着不求有功,但求无过地心思,goto一度被我扔到了垃圾篓。后来随着阅读代码量地增加,我发现goto至少在两个方面可起到改善程序地作用。一是出错处理,二是用来模仿递归。用来做出错处理,在某些特定的场合可以,增强阅读性。用来仿真递归,可以极大的提高程序的性能,但无疑会降低程序的可读性。这篇文章讨论后者。
我们来看一段代码:
求n—0范围内,所有整数的累加。
unsigned add( unsigned num)
{
if(num != 0) return num+add(num-1);
else return 0;
}
使用的时候有:
unsigned c=100;
cout<< add(c) <<endl;
这段程序简单的很,就是用递归求解,没什么好说。当然效率不会高,尤其num比较大的时候。这种影响是由于过于频繁的函数调用导致的。
现在我们来归纳一下这次递归调用的特征:
1. 由于递归函数原型一致,所以堆栈中存放的数据类型一致。也就是相当于一个数组。
2. 先压栈,增长堆栈大小,达到某个临界条件,开始出栈。并对出栈数据进行累加。出栈的次数当然同压栈的次数一致。
为了降低函数调用对性能的影响,我们来仿真这个过程。看如下程序和注释。
unsigned stack[100];//模拟堆栈,假设n为100
bool goback=false; //临界条件
int i=0; //计数
int p=c; //p=100
int num=0; //和
//相当于递归函数的入口
recurse:
if( p!=0)//进栈
{
stack[i++] = p--;
goto recurse;
}
else goback=true; //达到临界条件了
//出栈,求和,从递归中返回
if( --i >=0 )
{
num +=stack[i];
goto recurse;
}
这样实现,在空间和时间上都会有较佳的改善,当然前提是要用在恰当的地方。
最后说明一下,这个方法不是我发明的。Microsoft C/C++运行时库中的qsort就是用这种办法实现的。
分享到:
相关推荐
它只是将函数中的最终递归方法调用替换为goto到同一函数的开头。该项目使用执行字节码操作。例子倒数至零一个简单的尾递归函数,倒数为零:前后static void count( int n) { if (n == 0 ) { return ; } count(n - 1 ...
WHILE循环语句的翻译程序设计(递归下降法、输出三地址表示 对循环语句: WHILE〈表达式〉DO〈赋值语句〉 (1) 按给定的题目写出符合自身语法分析方法要求的文法和属性文法描述。 (2) 按给定的题目给出语法分析...
2、 递归与迭代程序 3、 递归数据结构 4、 递归程序及其验证 第六章 程序设计方法 1、 逐步求精方法 2、 模块化程序设计 3、 面向对象的程序设计 4、 面向Agent的程序设计 5、 面向COM的程序设计 6、 程序的形式化...
3.8 goto语句与标号 第四章 函数与程序结构 4.1 函数的基本知识 4.2 返回非整数型的函数 4.3 外部变量 4.4 作用域规则 4.5 头文件 4.6 静态变量 4.7 寄存器变量 4.8 程序块结构 4.9 初始化 4.10 递归 ...
1.9 goto关键字 1.10 void关键字 1.11 const关键字也被该被替换为readonly 1.12 最易变的关键字volatile 1.13 最会带帽子的关键字extern 1.14 struct关键字 1.15 union关键字 1.16 enum关键字 1.17 typedef关键字 第...
3.8 goto语句与标号 第4章 函数与程序结构 4.1 函数的基本知识 4.2 返回非整数值的函数 4.3 外部变量 4.4 作用域规则 4.5 头文件 4.6 静态变量 4.7 寄存器变量 4.8 分程序结构 4.9 初始化 4.10 递归 ...
3.8 goto语句与标号 第4章 函数与程序结构 4.1 函数的基本知识 4.2 返回非整数值的函数 4.3 外部变量 4.4 作用域规则 4.5 头文件 4.6 静态变量 4.7 寄存器变量 4.8 分程序结构 4.9 初始化 4.10 递归 ...
语法分析部分我们我们采用ll(1)方法实现,采用ll(1)方法实现语法发分析要求文法满足以下要求:经过压缩,无左递归,无回溯。 本部分内容是语义分析,主要的功能是把根据词法,语法分析的结果生成中间代码...
3.8 goto语句与标号 第4章 函数与程序结构 4.1 函数的基本知识 4.2 返回非整数值的函数 4.3 外部变量 4.4 作用域规则 4.5 头文件 4.6 静态变量 4.7 寄存器变量 4.8 分程序结构 4.9 初始化 4.10 递归 ...
3.8 goto语句与标号 第4章 函数与程序结构 4.1 函数的基本知识 4.2 返回非整数值的函数 4.3 外部变量 4.4 作用域规则 4.5 头文件 4.6 静态变量 4.7 寄存器变量 4.8 分程序结构 4.9 初始化 4.10 递归 ...
4.4.3 递归与循环的选择 108 4.4.4 递归函数实例 109 4.5 函数名重载 111 4.6 带缺省值的形式参数 114 4.7 内联函数 116 4.8 条件编译 119 4.8.1 基于多环境的程序编制 119 4.8.2 程序调试 122 4.9 标准库函数 123 ...
35 实例029 判断指定月份属于哪个季节 36 实例030 使用switch语句更改窗体颜色 37 实例031 循环向控制台中输入内容 38 实例032 递归算法的经典面试题 39 实例033 制作一个数字猜猜看小游戏 40 实例034 使用goto语句...
35 实例029 判断指定月份属于哪个季节 36 实例030 使用switch语句更改窗体颜色 37 实例031 循环向控制台中输入内容 38 实例032 递归算法的经典面试题 39 实例033 制作一个数字猜猜看小游戏 40 实例034 使用goto语句...
35 实例029 判断指定月份属于哪个季节 36 实例030 使用switch语句更改窗体颜色 37 实例031 循环向控制台中输入内容 38 实例032 递归算法的经典面试题 39 实例033 制作一个数字猜猜看小游戏 40 实例034 使用goto语句...
35 实例029 判断指定月份属于哪个季节 36 实例030 使用switch语句更改窗体颜色 37 实例031 循环向控制台中输入内容 38 实例032 递归算法的经典面试题 39 实例033 制作一个数字猜猜看小游戏 40 实例034 使用goto语句...
# 树函数(递归) def tree(d, s): if d return t.forward(s) tree(d - 1, s * .8) t.right(120) tree(d - 3, s * .5) t.right(120) tree(d - 3, s * .5) t.right(120) t.backward(s) #回退函数 ...
7.5.2标号与goto语句 7.5.3CASE语句的翻译 7.6过程调用的处理 7.7类型检查 7.7.1类型系统 7.7.2类型检查器的规格说明 7.7.3函数和运算符的重载 7.7.4多态函数 练 习 第八章符号表 8.1符号表的组织与作用 ...
6.2 goto语句及if-goto循环 (*) 6.3 while语句 (***) 6.4 do--while语句 (***) 6.5 for语句 (***) 6.6 循环嵌套 (***) 6.7 几种循环的比较 (*) 6.8 break语句和continue语句 6.9 程序举例 第七章 数组 ...
5.9 GOTO语句与标号 36 6 循环语句 36 6.1 WHILE 36 6.2 CONTINUE 37 6.3 BREAK 37 6.4 DO WHILE 37 6.5 FOR 37 6.6 循环嵌套 37 7 数组 38 7.1 一维数组定义与使用 38 7.2 数组在内存的存储方式 38 7.3 一维数组...
利用回溯法中的递归回溯方法 void nhuanghou(int a,int d[]) { int j,k; if(a>N) print(d); else for(j=1;j;) { if(a==1) { d[a]=j; /* printf("%d\n",j);*/ nhuanghou(a+1,d); } else { for(k=1;k;k...