递归算法
递归
注:此算法与 函数 有关,如不了解请移步。
在 wiki pedia 中,递归的解释是这样的:
在 C++ 中,递归就是指在函数中调用函数本身;递归的作用类似于分治,将一个大问题分解为很多小问题进行求解。
但是递归的时间复杂度极高,因为要解决很多小问题,所以时间复杂度高达
使用
递归必须要有一个出口!!!(你肯定不想要死循环,对吧?)
这个出口就是我们停止递归的条件,将问题解决了/分解到可以直接解决的程度了就推出递归。、
例题
例题 1
求
流程图如下:
代码为:
1 | int f(int n) |
例题 2
现在有一个斐波那契数列,求第
1 | int f(int n) |
记忆化搜索
记忆化搜索即为将之前递归出的量存储起来防止下次做重复的递归,此方法能有效地优化时间复杂度。
例:return ans[x] = f(x)
。
作者的话
作业:洛谷P1464
拜拜~
- 标题: 递归算法
- 作者: George222
- 创建于 : 2024-08-27 18:04:56
- 更新于 : 2024-09-12 17:40:27
- 链接: https://george110915.github.io/递归算法/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论