文章目录
- 一、使用递归推导斐波那契数列
- 1、问题分析
- 2、递归特点
- 3、递归内存开销
- 4、递归三要素
- 5、代码示例
一、使用递归推导斐波那契数列
斐波那契数列 : https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
1、问题分析
斐波那契数列分析 :
斐波那契数列 的 第 n 项 F(N) 依赖于 其第 n - 1 项 和 n - 2 项 相加的值 F(N - 1) F(N - 2) ;
该算法 可以使用 递归 进行解决 ;
2、递归特点
递归特点 :
递归就是 函数 自己 调用 自己 , 那么在 递归函数 中 , 需要一些参数变化 , 否则会一直不停的循环递归下去 ;
递归操作 类似于 给 洋葱剥皮 , 每次递归调用之后 , 整个问题的规模一直不断的变小 , 直到达到递归停止条件为止 ;
3、递归内存开销
递归的内存开销分析 : 函数执行时 , 需要在栈内存 中 存储当前函数的
- 函数参数列表
- 函数返回值
- 函数局部变量
每次递归都要 在 栈内存 中开辟 内存空间 存储本次调用函数的 参数列表 , 返回值 , 局部变量 , 如 : 函数参数是一个 int 类型值 , 则每递归一层 , 就要消耗 4 字节栈内存空间 ;
递归操作 每次调用 函数本身 , 都需要 在 栈内存 中 保存当前的调用细节 , 因此 递归操作 要消耗栈内存空间 , 如果递归的调用深度比较深 , 达到几十万次 , 有可能导致 栈内存溢出 StackOverflow ;
由于 递归 会消耗大量的栈内存空间 , 递归操作 能不用就不用 ;
递归第一层的 n , 与下面一层的 n 是不一样的 , 以 f(n) = f(n - 1) 2 , f(1) = 1 为例进行递归调用为例 ,
- 第一层调用的参数是 n , 栈内存空间保存该层调用数据 ,
- 第二层调用递归时 , 将 n - 1 作为 n 传递给了函数作为参数 , 栈内存空间保存该层调用数据 ,
- 直到调用到最底层 , f(1) = 1 , 开始逐层进行返回 , 每返回一层就会释放一层栈内存空间 ;
- 第二层调用递归时 , 将 n - 1 作为 n 传递给了函数作为参数 , 栈内存空间保存该层调用数据 ,
4、递归三要素
递归三要素 :
- 递归定义 : 分析函数的 参数 , 返回值 , 以及代表的含义 ;
- 递归拆解 : 分析每次 递归需要执行的操作 , 就是递归函数的具体内容 ;
- 递归出口 : 每个递归都需要一个 停止条件 , 递归不断循环会造成栈内存溢出 ;
5、代码示例
代码语言：javascript复制class Solution {
// 1. 递归定义 : 传入的 n 的含义是斐波那契数列的索引值,
// 返回值的含义是斐波那契数列的索引值对应的元素值
public int fib(int n) {
// 3. 递归出口 : 当递归执行到 n = 0 时, 开始逐层向上返回
if(n <= 1) {
return n;
}
// 2. 递归拆解 : n 索引的元素值 是 n - 1 和 n - 2 索引元素之和
return fib(n - 1) fib(n - 2);
}
}在 LeetCode 中不能使用递归推导 斐波那契数列 , 时间复杂度是 O(n^2) , 达不到要求 ;
