递归算法（Java)

目录

一定义.

二.用递归算法解决斐波拉契问题

一定义.

递归是一种算法思想，指函数直接或间接调用自身，将复杂问题分解为规模更小的子问题。递归的核心在于通过重复的自我调用解决问题，直到满足终止条件。

递归的基本要素：

1. 明确函数功能：定义函数的目标，例如计算阶乘函数的功能是返回一个数的阶乘。

2. 递归终止条件：确保递归不会无限循环，例如当输入为1时直接返回结果。

3. 等价关系式：将问题分解为子问题，例如阶乘公式 f(n) = n * f(n-1)。

递归需要遵守的重要规则
        1.执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
        2.方法的局部变量是独立的，不会相互影响，比如n变量
        3.如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
        4.递归必须向退出递归的条件逼近，否则就是无限递归,出现 StackOverflowError，死龟了:)
        5.当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

应用条件
满足下面3个条件可以运用递归算法解决问题。
（1）大问题可以转化为若干个小问题来求解，而这些小问题的求解 
方法与大问题相似，只是在数量规模上不同。
（2）递归调用的次数必须是有限的。
（3）必须有结束递归的条件来终止递归。

二.用递归算法解决斐波拉契问题

斐波拉契数形成的序列成为斐波拉契数列。该数列由0和1开始，后面的每一项数字是前面两个数字之和。

示例：

输入：3

输入2

过程：F(3)=F(1)+F(2)=1+1=2

现在我们用代码来实现一下

//用递归算法实现斐波拉契数列
public class DiguiTest
{
    private static Object Digui;

    //构造递归方法
    public int Digui(int n) {

        int result;
        if (n == 0)//如果n为0，返回0
        {
            return 0;
        }
        else if (n == 1)//如果n为1，返回1
        {
            return 1;
        } else
        {
            result = Digui(n - 1) + Digui(n - 2);//递归，返回前两项的和
        }
        return result;
    }
    public static void main(String[] args)
    {

        DiguiTest diguiTest = new DiguiTest();
        System.out.println("斐波拉契数列返回的值为："+diguiTest.Digui(3));
    }

}