关于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，其过程更加凝练，更具思想性，但相应不是十分直观。