递归基础斐波那契数（LeetCode——509.斐波那契数）

今天我们来学习一下递归：

什么是递归

  递归的核心思想是将一个复杂的问题分解成更小的、相似的子问题，直到这些子问题简单到可以直接解决。。在每个递归调用中，都会检查是否满足基本情况，如果满足，则返回一个直接的值，不再进行递归调用。没有基本情况，递归将无限进行下去，导致栈溢出错误。这是函数调用自身的过程。在这一步，问题被分解成更小的子问题，每个子问题都是原始问题的一个更小的版本。确保递归能够在有限的步骤内结束。通常通过基本情况来实现。

递归实例：

一个经典的递归例子是计算阶乘（n!），阶乘定义为所有小于或等于n的正整数的乘积。

public int factorial(int n) {
    if (n == 0) { // 基本情况
        return 1;
    } else {
        return n * factorial(n - 1); // 递归步骤
    }
}

 力扣题目

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/fibonacci-number?envType=problem-list-v2&envId=recursion递归解法：

class Solution {
    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int x = fib(n - 1);
        int y = fib(n - 2);
        return x + y;
    }
}

时间复杂度太高了，动态规划的时间复杂度会更低，可以初步了解一下，解法如下：

class Solution {
    public int fib(int n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        int a=0;
        int b=1;
        for(int i=2;i<=n;i++){
            int c=a+b;
            a=b;
            b=c;
        }
        return b;
    }
}