目录

递归三要素

1.求n的阶乘

2.斐波那契数列

理解递归对我们学习二叉树的遍历以及回溯的一些思想以及算法是很有必要的

递归三要素

1.明确递归方法实现功能

2.递归结束条件

3.方法等价关系式,提取其中的重复逻辑, 转化为规模更小的子问题,进入下一次递归,逼近递归结束条件

我们用这个三个条件看两个例子

1.求n的阶乘

package CsdnExample;

import java.util.ArrayList;
import java.util.List;

public class Sum{
    static int count=0;//定义一个静态成员变量 可以查看调用几次递归方法
    public static void main(String[] args) {
        System.out.println(sum(5));
        System.out.println(count);
    }
    public static int sum(int n){
        count++;
        if(n<=2){//递归结束条件
            return n;
        }
        return sum(n-1)*n;//转化为规模更小的子问题,进入下一次递归,逼近递归结束条件
    }
}//

 

我们可以看出递归调用了4次,具体调用如下图

2.斐波那契数列

斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34…，即第一项 f(1) = 1,第二项 f(2) = 1,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

package CsdnExample;

public class FeiBo {
    static int count=0;
    public static void main(String[] args) {
        System.out.println(fun(5));
        System.out.println(count);
    }
    public static int fun(int n){
        count++;
        if(n<=2){//递归终止条件
            return 1;
        }
        return fun(n-1)+fun(n-2);//转化为规模更小的子问题,向递归条件逼近
    }
}

 

我们将它抽象为一个递归树 就可以看出递归调用了9次此方法