無窮迴圈

(重定向自死循環

無窮迴圈endless loop)又称无穷回圈无限循环(infinite loop),是指程式控制流程一直在重複執行某一段程式碼,無法結束的情形,其原因可能是因為程式中的迴圈沒有設結束迴圈條件,或是結束迴圈的條件不可能成立等。在合作式多工(cooperative multitasking)的作業系統中,無窮迴圈會使系統沒有反應,若是先占式(preemptive)多工的系統中,無窮迴圈會用掉所有可用的處理器時間,不過可以由用戶結束程序。無窮迴圈是造成系統假死機的原因之一,其他的可能原因包括死鎖或是記憶體區段錯誤

忙碌等待迴圈是在外界特定條件時(例如有按鍵輸入)才會離開的迴圈,有時忙碌等待迴圈也被稱為是無窮迴圈,但此情形和上述的不太一樣。忙碌等待迴圈可以藉由外界事件而結束迴圈,但上述的無窮迴圈是無法結束的。

蓄意或無意產生的無窮迴圈

迴圈是指程式可能會重複執行的某一組指令,若重複執行,在特定條件成立後才會結束,若因為迴圈的特性,造成特定條件無法滿足,就會形成無窮迴圈。

蓄意產生的無窮迴圈

有些情形下程式會蓄意產生無窮迴圈。例如早期使用ROM匣的遊戲,在主程式的迴圈是無窮迴圈,沒有結束條件,原因是一般主程式若不執行時,系統控制權是交由作業系統,但這類遊戲沒有作業系統,因此讓主程式為無窮迴圈,程式會一直執行到斷電為止。

現在許多的電腦互動系統需要定期的監控用戶的輸入或是設備的活動,因此當系統閒置時,仍然會在無窮迴圈中執行,直到系統被重置或斷電為止。像在阿波罗计划導航用的電腦中,程式的最外層是無窮迴圈,若完全沒有其他工作要進行時,電腦會關閉「電腦運作中」的指示燈號。

無意產生的無窮迴圈

若程式中的無窮迴圈是無意產生的,也就是程序错误。新手程序員常常會出現這種错误,但在資深程序員身上也有可能發生,而且錯誤的原因可能相當微妙,因此不容易除錯。

 
循环链表可能會讓程式變成無窮迴圈

例如程序員想要從收集链表中所有的資料,因此會依链表依序前進,直到链表的尾端為止,但若程式未考慮链表可能是循环链表,在循环链表中依序前進的程序,反而會移動到链表較前面的部份,此時就會變成無窮迴圈。

大部份的無窮迴圈可以藉由詳細的的代碼檢視而找出,不過沒有通用的方式可以判斷程式是否會結束,或者會永遠執行(也就是無窮迴圈)。判斷程式會結束或會永遠執行的問題稱為停機問題,而英國電腦科學家艾伦·图灵证明了沒有停机问题的通用演算法[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的位置

X86組合語言的例子:

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……。像郵件循環英语e-mail loop就是這類的例子。

假無窮迴圈

假無窮迴圈是指一個迴圈看似不會結束,但只是一個執行很長時間,最後仍會結束的迴圈。

以下是一個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為止。

相關條目

參考資料

  1. ^ 謎樣的計算機科學之父
  2. ^ clang test.c -c -Wall
  3. ^ Alderson Loop页面存档备份,存于互联网档案馆) The Jargon File, Version 4.4.7. Accessed 5/21/2006. (public domain)