無窮迴圈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)