0基础学习Java（25）

递归（recursion）是一种常见的解决问题的方法，即把问题逐渐简单化。递归的基本思想就是“自己调用自己”，一个使用递归技术的方法将会直接或者间接的调用自己。利用递归可以用简单的程序来解决一些复杂的问题。比如：斐波那契数列的计算、汉诺塔、快速排序等问题。

【示例】使用递归实现斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）。

public class TestRecursion2 {

    public static void main(String[] args) {

        //使用循环实现       

        int num1 = 1;

int num2 = 1;

        int numn=0 ;

        int n= 40;

        long startTime = System.currentTimeMillis();

        for(int i=3;i<= n;i++ ){

            //得到i项的值

            numn = num1+ num2;

            //改变num2和num1的值

            num1 = num2;

            num2 = numn;       

        }

        System.out.println(n+"   "+numn);

        long endTime = System.currentTimeMillis();

        System.out.println("循环花费的时间："+(endTime - startTime));

 //使用递归实现

        startTime = System.currentTimeMillis();

        System.out.println(n+"   "+fibo(n));

        endTime = System.currentTimeMillis();

        System.out.println("递归 花费的时间："+(endTime - startTime));

    }   

    public static  int fibo(int n){//1,2,3.....n

        //给结果指定初始值

        int result = 0;      

        //使用递归求结果

        if(n==1 || n==2){

            result = 1;

        }else{

            result = fibo(n-2) + fibo(n-1);

        }    

        //返回结果

        return result;

    }

}

为方便大家学习   适合0基础学习Java的教学视频    大家可以跟着这个视频教程一起来学习Java

一个问题可被分解为若干层简单的子问题

子问题和其上层问题的解决方案一致

外层问题的解决依赖于子问题的解决

递归结构包括两个部分：

递归结束条件：什么时候不调用自身方法。如果没有条件，将陷入死循环。

递归体。解答：什么时候需要调用自身方法。为方便大家学习   适合0基础学习Java的教学视频    大家可以跟着这个视频教程一起来学习Java

递归的优点

自然的思路，简单的程序

递归的缺点

但是递归调用会占用大量的系统堆栈，内存耗用多，

在递归调用层次多时速度要比循环慢的多