NXT 無法使用遞歸 (Recursion)

http://4rdp.blogspot.com/2009/08/recursion.html

前些天在探奇自然科學教室看到一篇，解數獨的 NXT 機器人，利用NXT三顆馬達以及一顆光感應器，就可以掃描資料並辨識數字、解題，最後還可以填寫數獨答案，Tilted Twister 的設計者真是太厲害了。

該文邱老師提到遞歸(Recursion)一詞，除非讀者曾學過資料結構或是對電腦科學蠻了解，通常不知道那是啥東西。第一次學到遞歸這種方法是我在大學研習 PASCAL 這種語言才接觸到，現在的程式設計師除非有用過 Delphi，否則沒有機會再摸到這種即將絕種的電腦程式語言。

當初 PASCAL 被設計來教授電腦程式設計，它有非常嚴謹的語法，沒有正確定義過的字詞絕對無法編譯，就像規定小學生寫字要端端正正一樣，有太多語法限制，所以它就不容易成為主流的電腦程式語言。以個人經驗學好 BASIC 與 C 等主流電腦語言，幾乎各類程式都可以設計，若遇到一些冷僻的系統使用奇怪的程式語言，只要翻翻說明書很快可以觸類旁通。

關於遞歸，有兩本書可以參考，不過現在應該絕版了，
IBSN 0-8053-8384-0, An Introduction to the Art and Science of Programming: TURBO Pascal Edition, Walter J. Savitch
IBSN 0-88022-396-0, Using Turbo Pascal, Michael Yester

先看個簡單的例子，認識什麼是遞歸？
最大公因數 (Greatest Common Divisor) 大家應該都會，GCD1 是用 C 一般的寫法(疊代法，非遞歸法)，

unsigned int GCD1(unsigned int a, unsigned int b)
{
   unsigned int c;

   while (b != 0) {
      c = a % b;
      a = b;
      b = c;
   }

   return a;
}
 
unsigned int GCD2(unsigned int a, unsigned int b)
{
   unsigned int c;

   if (b == 0)
      c = a;
   else
      c = GCD2(b, a % b);

   return c;
}
 

舉個例子說明 GCD2，假設 a = 60，b = 36，那麼最大公因數為 12，數字標示表示第幾次執行。

a1 = 60, b1 = 36
a2 = 36, b2 = 24
a3 = 24, b3 = 12
c4 = a4 = 12, b4 = 0
c3 = c4 = GCD2(24, 12) = 12
c2 = c3 = GCD2(36, 24) = 12
c1 = c2 = GCD2(60, 36) = 12

使用遞歸有三項原則：
一、有重複的步驟，上面的例子程式自己呼叫自己。
二、越呼叫越簡單，上面的例子 a、b 數值越來越小。
三、必須有結束的方法，上面的例子 b = 0 沒有餘數就結束。

一般常人很難想到遞歸這種設計方法，除非遇到類似河內塔的問題，遞歸法才能輕易迎刃而解。

有興趣的同學，可以嘗試用 VB 或 VC 設計看看，至於 NXT 是無法使用 NXC 或 NXT-G 設計遞歸功能，因為 NXC compiler 限制不支援遞歸功能，而 NXT-G 是無法畫出函式中呼叫函式本身，對於 LabView 它應該可以畫出來，但是用於 NXT 我就不清楚了，如果仍然被限制使用的話，那表示 NXT 的作業系統限制使用堆疊 (Stack)。

2013.06.30 補充：圖解最大公因數計算