關于Karel倍增beeper問題的讨論

問題描述： 如下圖所示，Karel将從（1,1）出發尋找地圖中一處放置有若幹beeper的位置，将該處beeper數量double并傳回原點。

補充描述： Karel隻能在到達某處後獲知該處有或者沒有beeper，無法獲知具體數量。Karel隻能了解前進，轉向的指令。Karel在自己所在位置取出（如果有）beeper或者放下（如果有）beeper，一次隻能操作一個beeper。

 該程式分為三個部分，首先尋找beeper的放置位置，其次将該處的beeper數量增倍，最後傳回原處 這裡重點讨論第二部分。這裡的程式有兩種寫法： code 1： 通常做法，利用堆棧的方式，在旁邊空白位置處堆放2倍的beeper，再放回原處，程式如下

 
 private void doubleBeepers() {            
      
 //pick up beepers at the corner where they were put            
      
 //double them at the place behind this corner            
      
 while (beepersPresent()) {            
      
 pickBeeper();            
      
 turnAround();            
      
 move();            
      
 putBeeper();            
      
 putBeeper();            
      
 turnAround();            
      
 move();            
      
 }            
      
 //Pick up all the beepers generated at the new place            
      
 //return them back to their original place            
      
 turnAround();            
      
 move();            
      
 turnAround();            
      
 while (beepersPresent()) {            
      
 pickBeeper();            
      
 move();            
      
 putBeeper();            
      
 turnAround();            
      
 move();            
      
 turnAround();			            
      
 }		            
      
 }            
     
    

code 2：利用遞歸的思想将問題解構，進而避免在其餘空白處堆棧。原問題可以描述為取出一個beeper，将剩下的beeper加倍，再放入兩個beeper。那麼中間一個步驟又變為與原問題一緻的問題，也即将該處的beeper數量加倍。那麼設計一個方法（method），讓其反複調用自身，直至最後一步隻剩下一個beeper，取出後beeper不再存在，遞歸終止，繼而層層遞進依次兩兩放入beeper，進而實作了對于beeper數目的加倍。 代碼如下：

 
 private void recursionDoubleBeeper(){            
      
 if (beepersPresent()) {            
      
 pickBeeper();            
      
 recursionDoubleBeeper();            
      
 putBeeper();            
      
 putBeeper();            
      
 }             
      
 }            
     
    

讨論： 顯然方法2要遠優于方法1，其過程更加凝練，更具思想性，但相應不是十分直覺。