2009年9月5日 星期六

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 補充:圖解最大公因數計算

8 則留言:

  1. 根據John Hansen的說法是NXT的韌體不支援recursion。所以NXC也沒辦法使用recursion。
    (RobotC也沒有支援recursion)

    我想應該可以試著用疊代法解決問題。

    看來需要好好地再學一次『數值分析』

    Turbo PASCAL....真古老的東西。

    也讓我想起Fortran...... ^_^

    回覆刪除
  2. Hunter Chiou,

    謝謝您的補充說明,不過由此可知,您也是 NXT 程式設計高手。

    另外,從 FORTRAN 也些許透露出年齡 ... ^_^

    回覆刪除
  3. 我是探奇自然科學教室啦!

    不是設計高手.....

    真要透露年齡的話,我在國中時有用過『小神通』BASIC。

    啊!年紀大了總是會回想當年....^_^

    回覆刪除
  4. 原來是邱老師蒞臨,有失遠迎!

    太客氣了,NXT 方面您是專家,日後有機會想當面請教。

    對於 FORTRAN 等"古代"電腦程式語言,有空閒時,我會一一補充介紹,讓大家懷舊參考。 ^_^

    回覆刪除
  5. 您好想請問LEGO NXC裡面為何不能這樣寫?compile過不去?

    task A()
    {
    start main;
    }

    task main()
    {
    start A;
    }

    因為在網路上找資料找很久,後來發現這個好網站,於是跟您請教,謝謝!

    回覆刪除
  6. 0319 您好

    這個程式無法編譯,最主要的原因是受 NXT 韌體限制,詳細內容會另外專文討論,這裡先簡單回覆原因。

    NXT 的 OS 以及 你的程式,平時都是儲存在 flash 記憶體,執行時,你的程式會被搬移到 RAM 上去跑,這塊規劃的記憶體空間大小是固定的,你的程式使用多少變數,OS 就配給多少記憶空間給你的程式,不會提供多餘記憶體。

    一般 OS 執行副程式時會額外需求記憶空間,這會佔用堆疊,以確保副程式執行完畢,可以回到原來主程式,您提供的例子,兩程式相互呼叫,這樣堆疊會被永無止境新增佔用,最後所有 RAM 被這兩程式完全佔用,連OS 的空間也不會放過,如果這樣的程式是可以被執行的話,NXT 就會發生當機。

    所以 NXT OS 禁止 recursion,同樣配合NXT 開發工具程式都會被限制,不然跑錯程式,造成 NXT 當機無法使用,反而造成更多"民怨"!

    回覆刪除
  7. 謝謝這麼詳盡的解答,感謝!

    另外請教老師,task為何在順序上也有很多限制?

    譬如說,為何只能上面的task不能start下面的task?

    task A()
    {
    start B;
    }

    task B()
    {
    ...
    }
    這樣task在排序上常常出現問題?謝謝!

    回覆刪除
  8. 0319 您好,

    這是編譯器 (Compiler) 的設計問題,編譯器的用途是將你所寫的程式文字,轉換為可執行機械碼,設計良好的編譯器,不會有程式位置次序問題。

    NXC 編譯器設計,它是循序編譯,因為 task A 先編譯而 task B 還沒編譯,所以編譯 Start B 這一行時,編譯器不認識 task B 因此產生錯誤。

    如果 task A 與 task B 位置對調,那麼就沒問題。

    專業的高級編譯器處理這種問題,會先產生中繼檔,task A 編譯連結 (Link) 時,會搜尋中繼檔內 task B 是否存在,這樣就可以解決程式位置問題。

    知道這樣,在 NXC 還未改善前,寫程式時應避開這類狀況。

    回覆刪除