递归及其替代算法

import java.util.LinkedList;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MoveAction;

import com.sun.corba.se.spi.orbutil.fsm.State;
import com.sun.org.apache.xpath.internal.functions.Function;

/**
 * 递归算法,递归的非递归替代算法
 *
 */
public class TestRecursion
{
  // 题目:计算给定文本内字符“a”的个数。分别用迭代和递归两种方式。
  /**
   * 常规算法
   */
  public int countACommon(String str)
  {
    int count = 0;
    String tmpString = str;
    while (tmpString.indexOf("a") >= 0)
    {
      count++;
      tmpString = tmpString.substring(tmpString.indexOf("a") + 1);
    }
    return count;
  }

  /**
   * 递归算法
   */
  public int countARecursion(String str)
  {
    String tmpStr = str;
    if (tmpStr.indexOf("a") < 0) return 0; // 递归退出条件
    else return countARecursion(tmpStr.substring(tmpStr.indexOf("a") + 1)) + 1;

  }

  /**
   * 斐波那契数列 项,非递归(速度快,求第10000项毫无压力)
   */
  public int f(int n)
  {
    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 1;

    int i, s = 0;
    int s1 = 1, s2 = 1;
    for (i = 3; i <= n; i++)
    {
      s = s1 + s2;
      s2 = s1;
      s1 = s;
    }
    return s;
  }

  /**
   * 单向递归是指递归算法中虽然有多处递归调用语句，
   * 但各递归调用语句的参数之间没有关系，
   * 并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。
   * 斐波那契数列 项,递归(求第100项时就扛不住了)
   * 1 1 2 3 5 8 13
   */
  public int f2(int n)
  {
    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 1;

    return f2(n - 2) + f2(n - 1);
  }

  /**
   * 求阶乘,非递归,最大求31,超过31!,int就不够用了
   * @param n
   * @return
   */
  public int factorial(int n)
  {
    if (n < 0) return 0;
    if (n == 0) return 1;
    if (n == 0) return 1;
    int s = 1;
    for (int i = 1; i <= n; i++)
    {
      s = s * i;
    }
    return s;
  }

  /**
   * 求阶乘,递归算法,最大求31,超过31!,int就不够用了
   * @param n
   * @return
   */
  public int factorial_R(int n)
  {
    if (n < 0) return 0;
    if (n == 0) return 1;
    if (n == 0) return 1;
    return n * factorial_R(n - 1);
  }

  /**
   * 汉诺塔,递归算法(将A上面的盘子,借助B,移动到C上面)
   * @param n 需要移动的盘子个数
   * @param A 盘子所在的原始位置
   * @param C 盘子的目标位置
   * @param B 移动盘子借助的位置
   */
  public void hanoi_R(int n, String A, String B, String C)
  {
    if(n == 1) move(n,A,C); //只有一个盘子,直接移
    else 
    {
      hanoi(n - 1,A,C,B); // 先将n-1个盘子,从A移动到B,借助C
      move(n,A,C);        //将最后一个盘子 直接 从A移动到目标位置C,此时A空下来,B上面有n-1个盘子
      hanoi(n-1,B,A,C);   //将B上面的n-1个盘子,借助A,移动到C
    }
  }

  private void move(int n,String from ,String to)
  {
    //System.out.println("move " + n + ": " + from + " --> " + to);
  }
  
  
  /**
   * 非递归算法,使用栈,HanoiItem栈对象,以保存相关中间信息
   */
  class HanoiItem
  {
    public int count;                 //可以直接移动的盘子的编号
    public boolean flag = false;      //flag = true 说明可以直接移动
    public String currentPlace;       //当前位置
    public String assistantPlace;     //辅助位置
    public String destinationPlace;   //目标位置
    
    public HanoiItem(int count,boolean flag,String currentPlace,String assistantPlace,String destinationPlace)
    {
      this.count = count;
      this.flag = flag; //只有一个盘子表示可以直接移动
      if(count==1) this.flag = true; //重要: 如果只有一个盘子,表示可以直接移动
      this.currentPlace = currentPlace;
      this.assistantPlace = assistantPlace;
      this.destinationPlace = destinationPlace;
    }
    
    public void move()
    {
      //System.out.println("move " + this.count + ": " + currentPlace + " --> " + destinationPlace);
    }
  }
  
  /**
   * 将初始状态s0进栈
   * while (栈不为空)
   * {
   *    退栈，将栈顶元素赋给s;
   *    if (s是要找的结果) 返回;
   *    else 
   *    {
   *      寻找到s的相关状态s1;
   *      将s1进栈;
   *    }
   * }
   * 
   */
  
  public void hanoi(int n, String A, String B, String C)
  {
    if(n == 1) move(n,A,C); //只有一个盘子,直接移
    else 
    {
      //初始化一个栈,LinkedList可以当栈使用
      LinkedList<HanoiItem> stack = new LinkedList<HanoiItem>();
      HanoiItem initHanoi = new HanoiItem(n, false, A, B, C);
      stack.push(initHanoi);  //将初始状态s0进栈
      
      while(stack.size()>0) //while (栈不为空)
      {
        HanoiItem tempItem = stack.pop(); //退栈，将栈顶元素赋给s;
        if(tempItem.flag) //if (s是要找的结果) 返回;
        {
          tempItem.move();
        }
        else  //寻找到s的相关状态s1; 这里相关的状态有三个
        {
          //表示需要将上面的n-1个盘子 借助于 目标位置 ,整体先移动到 中间(协助用)的 杆子
          HanoiItem ItemBefore = new HanoiItem(tempItem.count - 1,false,tempItem.currentPlace,tempItem.destinationPlace,tempItem.assistantPlace);
          //表示将最后一个盘子移动到目标位置
          HanoiItem itemCurr = new HanoiItem(tempItem.count,true,tempItem.currentPlace,tempItem.assistantPlace,tempItem.destinationPlace);
          //表示将 前面已经移动到中间杆子上的盘子,借助第一个杆子 移动到 目标位置
          HanoiItem itemAfter = new HanoiItem(tempItem.count -1,false,tempItem.assistantPlace,tempItem.currentPlace,tempItem.destinationPlace);
          
          //将上面三个中间状态入栈,注意顺序,栈先进后出,所以入栈顺序要反过来
          stack.push(itemAfter);
          stack.push(itemCurr);
          stack.push(ItemBefore);
        }
      }
    }
  }

  public static void main(String[] args)
  {
    String tmpString = "aaa";
    TestRecursion test = new TestRecursion();
    System.out.println(test.countACommon(tmpString));
    System.out.println(test.countARecursion(tmpString));
    System.out.println(test.factorial_R(5));
    
    //递归汉诺塔
    long s1 = System.currentTimeMillis();
    test.hanoi_R(15,"A","B","C");
    long e1 = System.currentTimeMillis();
    System.out.println(e1 - s1); //移动,10层,0,15层 16, 20层,140,25层 3547, 30层 112830
    
    //非递归
    System.out.println("-----------------------------------");
    long s2 = System.currentTimeMillis();
    test.hanoi(15,"A","B","C");
    long e2 = System.currentTimeMillis();
    System.out.println(e2 - s2); 
    //移动10层 16, 15层 16, 20层 110,25层 3453,30层 114596,
    //貌似因为递归使用了太多的中间对象,而且LinkedList效率貌似不高

  }
}

//递归:     移动,10层 0, 15层 16, 20层  140, 25层 3547, 30层 112830
//非递归:   移动 10层 16, 15层 16, 20层 110, 25层 3453, 30层 114596,