Java中的递归算法

递归调用：方法自己调用自己的现象就称为递归。

通俗的来说就是方法调用其本身！！！！！！！！！！

递归有三大要素：
1.递归出口

2.参数

3.递归方法

递归的分类:

• 递归分为两种，直接递归和间接递归。

• 直接递归称为方法自身调用自己。

• 间接递归可以A方法调用B方法，B方法调用C方法，C方法调用A方法。

注意事项：

• 递归一定要有条件限定，保证递归能够停止下来，否则会发生栈内存溢出。

• 在递归中虽然有限定条件，但是递归深度不能太深，否则效率低下，或者也会发生栈内存溢出。

  • 能够使用循环代替的，尽量使用循环代替递归

案例：计算斐波那契数列（Fibonacci）的第n个值，斐波那契数列满足如下规律，

1,1,2,3,5,8,13,21,....

即从第三个数开始，一个数等于前两个数之和。假设f(n)代表斐波那契数列的第n个值，那么f(n)满足：

f(n) = f(n-2) + f(n-1);

package com.atguigu.test07.recursion;public class FibonacciTest {public static void main(String[] args) {FibonacciTest t = new FibonacciTest();//创建FibonacciTest的对象，目的是为了调用f方法for(int i=1; i<=10; i++){System.out.println("斐波那契数列第" +i +"个数:" + t.f(i));}System.out.println(t.f(20));//6765   }//使用递归的写法int f(int n){//计算斐波那契数列第n个值是多少if(n<1){//负数是返回特殊值1，表示不计算负数情况return 1;}if(n==1 || n==2){return 1;}return f(n-2) + f(n-1);}
}

package com.atguigu.exer.recursion;public class FibonacciTest {public static void main(String[] args) {FibonacciTest t = new FibonacciTest();//创建FibonacciTest的对象，目的是为了调用f方法for(int i=1; i<=10; i++){System.out.println("斐波那契数列第" +i +"个数:" + t.fValue(i));}System.out.println(t.fValue(20));//6765}//不用递归int fValue(int n){//计算斐波那契数列第n个值是多少if(n<1){//负数是返回特殊值1，表示不计算负数情况return 1;}if(n==1 || n==2){return 1;}//从第三个数开始，  等于 前两个整数相加int beforeBefore = 1; //相当于n=1时的值int before = 1;//相当于n=2时的值int current = beforeBefore + before; //相当于n=3的值//再完后for(int i=4; i<=n; i++){beforeBefore = before;before = current;current = beforeBefore + before;/*假设i=4beforeBefore = before; //相当于n=2时的值before = current; //相当于n=3的值current = beforeBefore + before; //相当于n = 4的值假设i=5beforeBefore = before; //相当于n=3的值before = current; //相当于n = 4的值current = beforeBefore + before; //相当于n = 5的值....*/}return current;}}