递归算法

1.何为递归

个人理解就是自己调用自己，直到满足一个条件结束自己调用自己的过程，这个就是递归。

 

2.递归算法设计的基本思想是：

对于一个复杂的问题，把原问题分解为若干个相对简单类同的子问题，继续下去直到子问题简单到能够直接求解，也就是说到了递推的出口，这样原问题就有递推得解。 
关键要抓住的是： 
（1）递归出口 
（2）地推逐步向出口逼近 

3.常见递归算法

（1）最常见的就是阶乘，比如求5的阶乘，数学公式就是：5*4*3*2*1，代码：

 

package suanfa;
/**
 * Created by tl on 2016/4/10.
 */
public class Digui {
    public static int digui(int n){
        if(n==1||n==0){
            return n;
        }else{
            System.out.println("执行第" + n + "次");
            return n*digui(n-1);
        }
    }
public static void main (String[] args){
    System.out.print(digui(5));
}

 

（2）求1+2+3+4+5+6+7……+1000的和

 

    static int  count(int n){
        if(n>0){
            return n+count(n-1);
        }else{
            return 0;
        }

    }

    public static void main(String args[])
    {
        int sum=count(1000);
        System.out.println(sum);
    }
}

（3）1,1,2,3,5,8,13,21,34...，求用递归算第30个数

 

 

static int count(int n){
    if(n==1||n==2) {
        return 1;
    }
     return count(n-1)+count(n-2);
}

public static void main(String args[])
{
    int sum=count(30);
    System.out.println(sum);
}