Android 算法之递归

定义

在数学与计算机科学中，递归(Recursion)是指在函数的定义中使用函数自身的方法。
递归的三要素：

• 明确递归终止条件
• 给出递归终止时的处理办法
• 提取重复的逻辑，缩小问题规模

递归的应用场景：

1. 问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；
2. 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；
3. 数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）。

实例

1. 九九乘法表

public class Main {
    public static void main(String[] args) {
        method(9);
    }
    
    private static void method(int i) {
        if (i == 1) {  
            System.out.println("1*1=1 "); 
        } else {  
            method(i - 1); 
            for (int j = 1; j <= i; j++) { 
                System.out.print(j + "*" + i + "=" + j * i +  "  ");  
            }  
            System.out.println();  
        }
    }

}

2. 阶乘

public class Main {
    public static void main(String[] args) {
        System.out.print(method(10));
    }
    
    public static long method(int n){
        if(n == 1) {
           return 1;     
        } 
        return n*method(n-1); 
    }

}

3. 斐波纳契数列

public class Main {
    public static void main(String[] args) {
        System.out.print(fibonacci(1,1,8));
    }
    
    /**
     * @description 经典递归法求解
     * 
     * 斐波那契数列如下：
     * 
     *  1,1,2,3,5,8,13,21,34,...
     * 
     * *那么，计算fib(5)时，需要计算1次fib(4),2次fib(3),3次fib(2)，调用了2次fib(1)*，即：
     * 
     *  fib(5) = fib(4) + fib(3)
     *  
     *  fib(4) = fib(3) + fib(2) ；fib(3) = fib(2) + fib(1)
     *  
     *  fib(3) = fib(2) + fib(1)
     *  
     * 这里面包含了许多重复计算，而实际上我们只需计算fib(4)、fib(3)、fib(2)和fib(1)各一次即可，
     * 后面的optimizeFibonacci函数进行了优化，使时间复杂度降到了O(n).
     * 
     * @author rico
     * @created 2017年5月10日 下午12:00:42
     * @param n
     * @return
     */
    public static int fibonacci(int first, int second, int n) {
        if (n > 0) {
            if(n == 1){    // 递归终止条件
                return first;       // 简单情景
            }else if(n == 2){            // 递归终止条件
                return second;      // 简单情景
            }else if (n == 3) {         // 递归终止条件
                return first + second;      // 简单情景
            }
            return fibonacci(second, first + second, n - 1);  // 相同重复逻辑，缩小问题规模
        }
        return -1;
    }

}

4. 杨辉三角

public class Main {
    public static void main(String[] args) {
        int length = 10;    // 打印的行数
    
        for (int i = 1; i <= length; i++) {
            // 打印空格
            for (int j = 1; j <= length-i; j++) {
                System.out.print("  ");
            }
            for (int j = 1; j <= i; j++) {
              System.out.printf("%4d",fun(i,j));
            }
          System.out.println();
        }
  }
    
/**
    * Title: 杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。
    * 它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。
    * 
    * 例如，下面给出了杨辉三角形的前4行： 
    *    1 
    *   1 1
    *  1 2 1
    * 1 3 3 1
    * @description 递归获取杨辉三角指定行、列(从0开始)的值
    *              注意：与是否创建杨辉三角无关
    * @author rico 
    * @x  指定行
    * @y  指定列  
    */
    public static int fun(int i,int j) {
    if(j == 1 || i == j) {
      return 1;
    }else {
      return fun(i-1,j)+fun(i-1,j-1);
    }
  }

}

5. 回文字符串的判断

      /*
      * Title: 回文字符串的判断
      * Description: 回文字符串就是正读倒读都一样的字符串。如”98789”, “abccba”都是回文字符串
      **/
public class Main {
    public static void main(String[] args) {
        System.out.print(method("abccba"));
    }
    
    public static boolean method(String s) {
        int start = 0;
        int end = s.length()-1;
        if(end > start) {   
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }else{
                return method(s.substring(start+1).substring(0, end-1));
            }
        }
        return true;
    }

}