递归算法

1. 方法体中调用方法自己本身
2. 递归算法的方法体中一定要出现递归的出口,否则会抛出java.lang.StackOverflowError - 堆栈溢出错误

使用场景:适合解决大量的,重复性的业务题

缺点:性能比较低,将每次计算的结果都会保存在内存中.

案例

1. 求某个数的阶乘 ※

   /**
        * n!
        * @param n
        * @return
        */
   public static int jie(int n){
     //如果没有出口 - java.lang.StackOverflowError 堆栈溢出错误
     //1. 第一个位置都是1
     if(n==1)
       return 1;
   
     //2. 方法体中调用自己
     return n*jie(n-1);
     //     6*jie(5)
     //     6*5*4*3*2*1
   }
   

2. 斐波那契数列 ※

   //斐波那契数列
   //1 1 2 3 5 8 13 21 34 55 ...
   public static int fei(int n){
     if(n == 1 || n==2)
       return 1;
     return fei(n-1) + fei(n-2);
     //n=4
     //fei(3)+fei(2)
     //fei(2) + fei(1) + fei(2)=3
   }
   

3. 求最大公约数

   //求最大公约数
   public static int commonDivisor(int m,int n){
     if(m % n ==0)
       return n;
     return commonDivisor(n,m%n);
   }
   

4. 求杨辉三角某行某列的值

    /**
        *    1
        *    1 1
        *    1 2 1
        *    1 3 3 1
        *    1 4 6 4 1
        *    1 5 10 10 5 1
        *
        * @param x 纵坐标 行
        * @param y 横坐标 列
        * @return
        */
   public static int yang(int x,int y){
     if(y==0 || x==y)
       return 1;
     return yang(x-1,y-1) + yang(x-1,y);
   }
   

5. 打印直角三角形杨辉三角

      
   /**
        * 打印直角三角形.
        * @param x 打印的杨辉三角的行数
        */
   public static void printYang(int x){
     for (int i = 0; i < x; i++) {
       for (int j = 0; j <=i ; j++) {
         System.out.print(yang(i,j)+"\t");
       }
       System.out.println();
     }
   }