无穷回圈
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
循环结构 |
---|
do-while循环 |
while循环 |
for循环 |
foreach循环 |
死循环 |
无穷回圈(endless loop)又称无穷回圈、无限循环(infinite loop),是指程式的控制流程一直在重复执行某一段程式码,无法结束的情形,其原因可能是因为程式中的回圈没有设结束回圈条件,或是结束回圈的条件不可能成立等。在合作式多工(cooperative multitasking)的作业系统中,无穷回圈会使系统没有反应,若是先占式(preemptive)多工的系统中,无穷回圈会用掉所有可用的处理器时间,不过可以由用户结束程序。无穷回圈是造成系统假死机的原因之一,其他的可能原因包括死锁或是记忆体区段错误。
忙碌等待回圈是在外界特定条件时(例如有按键输入)才会离开的回圈,有时忙碌等待回圈也被称为是无穷回圈,但此情形和上述的不太一样。忙碌等待回圈可以借由外界事件而结束回圈,但上述的无穷回圈是无法结束的。
蓄意或无意产生的无穷回圈
[编辑]回圈是指程式可能会重复执行的某一组指令,若重复执行,在特定条件成立后才会结束,若因为回圈的特性,造成特定条件无法满足,就会形成无穷回圈。
蓄意产生的无穷回圈
[编辑]有些情形下程式会蓄意产生无穷回圈。例如早期使用ROM匣的游戏,在主程式的回圈是无穷回圈,没有结束条件,原因是一般主程式若不执行时,系统控制权是交由作业系统,但这类游戏没有作业系统,因此让主程式为无穷回圈,程式会一直执行到断电为止。
现在许多的电脑互动系统需要定期的监控用户的输入或是设备的活动,因此当系统闲置时,仍然会在无穷回圈中执行,直到系统被重置或断电为止。像在阿波罗计划导航用的电脑中,程式的最外层是无穷回圈,若完全没有其他工作要进行时,电脑会关闭“电脑运作中”的指示灯号。
无意产生的无穷回圈
[编辑]若程式中的无穷回圈是无意产生的,也就是程序错误。新手程序员常常会出现这种错误,但在资深程序员身上也有可能发生,而且错误的原因可能相当微妙,因此不容易除错。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Circularly-linked-list.svg/300px-Circularly-linked-list.svg.png)
例如程序员想要从收集链表中所有的资料,因此会依链表依序前进,直到链表的尾端为止,但若程式未考虑链表可能是循环链表,在循环链表中依序前进的程序,反而会移动到链表较前面的部份,此时就会变成无穷回圈。
大部份的无穷回圈可以借由详细的的代码检视而找出,不过没有通用的方式可以判断程式是否会结束,或者会永远执行(也就是无穷回圈)。判断程式会结束或会永远执行的问题称为停机问题,而英国电脑科学家艾伦·图灵证明了没有停机问题的通用演算法[1]。
举例
[编辑]以下是一些无穷回圈的例子。
C语言的无穷回圈:
#include <stdio.h>
main()
{
while(1) {
printf("Infinite Loop\n");//顯示"Infinite Loop"字串
}
}
上述程式会一直显示"Infinite Loop"字串。
BASIC语言的无穷回圈:
10 PRINT "Infinite Loop"
20 GOTO 10'跳到行號=10的位置
loop:
;空的無窮迴圈,直接跳到"loop"標籤的位置
jmp loop
Python的例子:
while True:
print("Infinite Loop")#顯示"Infinite Loop"字串
逻辑错误
[编辑]以下是一个Visual Basic无穷回圈的例子:
dim x as integer
do until x > 5 '根本不會有x>5的情形
x = 1
x = x + 1
loop
每一次执行回圈时x会先设定为1,然后变为2,因为数值未大于5,所以永远不会结束。若将x = 1
由回圈内部移到回圈之前即可以改善此一情形。
有些程序员可能因为不熟悉特定程式语言的语法而造成无穷回圈,例如以下是一段C语言的程式:
#include <stdio.h>
main()
{
int a = 0;
while (a < 10) {
printf("%d\n", a);
if (a = 5) {//a設定為5,進入無窮迴圈
printf("a equals 5!\n");
}
a++;
}
return 0;
}
其预期输出是数字0至9,其中5和6中间会显示"a equals 5!",但程序员在编写程式时将设定用的=
运算子及判断相同的==
运算子弄混了,因此程式会在每次执行回圈时都会将a设定为5,因此变数a永远无法到达10,此回圈就变成了无穷回圈。
现代化的编译器,例如clang,都已经可以检测到这一类的潜在问题并给出警告。[2]
变数处理错误
[编辑]有时不适当的回圈结束条件也可能会造成无预期的无穷回圈,例如以下C语言的例子:
float x = 0.1;
while (x != 1.1) {//可能會因為浮點運算的誤差而出現問題
printf("x = %f\n", x);
x = x + 0.1;
}
在有些作业系统中,上述程式会执行10次回圈然后结束,但有些系统中,上述程式却可能会一直执行,无法结束,问题主要在回圈的结束条件(x != 1.1)要在二个浮点数相等时才结束,结果会依系统处理浮点数的方式而定,只要系统执行10次回圈后的结果和1.1差一点点,上述程式就会变成无穷回圈。
若将结束条件改为(x < 1.1)就没有这个问题,程式可能会多执行一次回圈,但不会变成无穷回圈。另一种解决方式则是用一个整数变数作为回圈变数,再依此变数判断是否要结束回圈。
在数值分析程式中也可能会出现无预期的无穷回圈,例如程式需一直迭代到误差小于某特定值为止,但若因为运算中的舍去误差,使得误差一直无法小于该特定值,就会产生无穷回圈。
奥尔德森回圈
[编辑]奥尔德森回圈(Alderson loop)是指一个回圈有设定结束条件,但因为程式的写法(多半是编程错误),造成永远无法满足结束条件,在针对使用者介面程式侦错时最容易出现这类的问题。
以下C的虚拟码中有一个奥尔德森回圈,程式是要计算使用者输入一串数字的和,使用者输入0时结束回圈,但程式中用了不正确的运算符:
sum = 0;
while (true) {
printf("Input a number to add to the sum or 0 to quit");
i = getUserInput();
if (i * 0) { // 若i乘0为真,则使sum加上i的值
sum += i; // 但这不可能发生,因为不论i为何值(i * 0)都是0。如果条件中用的是!=而非*,代码就能正常运行
}
if (sum > 100) {
break; // 终止循环。结束条件存在,但从来没有达到过,因为sum永远不会增加
}
}
“奥尔德森回圈”来自一个Microsoft Access的程式设计师,他编写的程式产生一个有模式的对话框,使用者需要回应,程式才能继续运作,但对话框没有OK键或取消键,因此只要此对话窗出现,Access程式就无法继续运作[3]。
无穷递回
[编辑]无穷递回是一种由递归造成的无穷回圈。例如以下计算阶乘的C语言程式:
unsigned int fac(unsigned int a)
{//n!=n*(n-1)!
return( fac(a-1) * a);
}
一般递回的程式会有一特定条件,此条件成立时直接计算结果,而不是透过递回来计算结果,若程式中未定义此条件,就会出现无穷递回。
无穷递回会造成堆叠溢位,而无穷递回不会结束,因此也是无穷回圈的一种。不过若递回程式是使用尾端递回的处理方式,在有些程式语言(如Scheme)中会优化成回圈,因此不会造成堆叠溢位。
上述的程式可以修改成没有无穷递回的程式。
unsigned int fac(unsigned int a)
{
if (a == 0) {//定義0!=1
return 1;
}
else {
return( fac(a-1) * a);
}
}
多个模组产生的无穷回圈
[编辑]无穷回圈也可能因为多个模组之间的互动而产生。考虑一台伺服器若收到无法理解的需求时,会回应错误讯息,此架构中不会有无穷回圈。但若有二台上述的伺服器(A和B),互相交换资料,A收到由B所送出无法理解的需求,会回应错误讯息给B,但若B也无法理解A送出的需求(其实是A的错误讯息),会再以自己的格式回应错误讯息给,A收到后无法理解,会再回应错误讯息给B……。像邮件循环就是这类的例子。
假无穷回圈
[编辑]假无穷回圈是指一个回圈看似不会结束,但只是一个执行很长时间,最后仍会结束的回圈。
以下是一个C语言for回圈的程式:
unsigned int i;
for (i = 1; i != 0; i++) {
/* loop code */
}
上述程式每次执行时都将i加1,若i等于0时才会结束回圈,此程式看似不会结束,但最后还是会结束。程式中型态为unsigned int
的变数,其数值有一定上限,当数值已到上限,再加1时,变数数值就会变为0,因此让程式结束。实际的上限值依系统及编译器而不同,假如unsigned int
是一个16个位元的字元组,上述的回圈会执行65536次。若使用高精度计算,程式会一直执行到记忆体无法储存i
为止。
相关条目
[编辑]参考资料
[编辑]- ^ 谜样的计算机科学之父
- ^ clang test.c -c -Wall
- ^ Alderson Loop (页面存档备份,存于互联网档案馆) The Jargon File, Version 4.4.7. Accessed 5/21/2006. (public domain)