遞歸的執行個體-Java

遞歸執行個體

/**
 * 對遞歸進行訓練
 * 
 * @author Clearlight
 *
 */
public class _07_遞歸 {

  public static void main(String[] args) {
    System.out.println(f1(3)); // n的階乘
    System.out.println(f2(new int[] {1,1,2,3,4},0)); // 對arr的所有元素求和,從頭開始
    System.out.println(f21(new int[] {1,1,2,3,4},4)); // 對arr的所有元素求和,從尾開始
    System.out.println(f3("abcde",4)); // 翻轉字元串
    System.out.println(f4(6)); // 斐波那契數列
    System.out.println(f5("aaab","aaa")); // 比較兩個字元串是否相等
  }

  /**
   * 需求:遞歸求解階乘
   * 
   * 思路:
   * f(n):求n的階乘-->f(n-1)求n-1的階乘
   * 找重複:n*(n-1)的階乘,求n-1的階乘是原問題的重複(規模更小)－子問題
   * 找變化:變化的量應該作為參數
   * 找邊界:出口
   * 
   * @param n 開始的數
   * @return 傳回結果
   */
  static int f1(int n) {
    if (n == 0) {
      return 1;
    }
    return n * f(n - 1);
  }
  
  /**
   * 需求: 對arr的所有元素求和,a[begin] + (begin+1...結束)
   * 
   * @param arr
   * @param begin
   * @return
   */
  static int f2(int[] arr, int begin) {
    if(begin == arr.length-1) {
      return arr[begin];
    }
    // 類似踢皮球
    return arr[begin] + f2(arr,begin+1);
  }
  
  /**
   * 需求: 對arr的所有元素求和,a[end-1...0) + a[end]
   * 
   * @param arr
   * @param end
   * @return
   */
  static int f21(int[] arr, int end) {
    if(end == 0) {
      return arr[0];
    }
    return arr[end] + f2(arr, end-1);
  }
  
  
  /**
   * 需求: 翻轉字元串
   * 
   * @param src
   * @param end
   * @return
   */
  static String f3(String src, int end) {
    if(end == 0) {
      return "" + src.charAt(0);
    }
    return src.charAt(end) + f3(src, end-1);
  }
  
  
  /**
   * 需求: 求斐波那契數列
   * 
   * @param n 第n個位置
   * @return 傳回第n個位置的值
   */
  static int f4(int n) {
    if(n==1||n==2) {
      return 1;
    }
    return f4(n-1) + f4(n-2);
  }
  
  /**
   * 需求 : 比較兩個字元串是否相等
   * 
   * @param s1
   * @param s2
   * @return
   */
  public static boolean f5(String s1, String s2) {
    
    if(s1.length() != s2.length()) {
      return false;
    }
    if(s1.length() == 0) {
      return true;
    }
    
    if(s1.charAt(0) != s2.charAt(0)) {
      return false;
    }
    
    return f5(s1.substring(1),s2.substring(1));
  }
}

/*
輸出:
6
11
11
edcba
8
false
*/      

其他遞歸例題