递归算法入门超详解（阶乘｜斐波那契记忆化｜汉诺塔）

递归篇文章目录递归篇引言1.递归1.1递归表象1.2递归特点2.典型递归2.1阶乘2.2斐波那契数列2.2.1普通暴力递归2.2.2记忆化递归优化思想2.3汉诺塔问题描述递归思路数学递归式3.如何编写递归函数3.1步骤3.2递归本质:4.总结引言递归是算法最重要的基础思想也是 DFS、回溯、分治、动态规划的前置知识点。1.递归可以衍生出指数级的内容 并且会呈现出树状结构1.1递归表象自身调用自身递归两大核心组成基线条件递归出口已知、可直接求解的最小子问题必须写否则无限递归、栈溢出。递归式子把原问题拆解为规模更小的同类型子问题子问题求解完成后合并结果。执行分为两个阶段向下递推一层层调用自己把大问题拆小直到命中基线条件。向上回溯拿到子问题的返回结果向上计算逐层返回。1.2递归特点结构天然树形展开普通无优化递归容易产生大量重复计算可以通过记忆化搜索优化为线性时间2.典型递归2.1阶乘f(5)f(4)*5;f(4)f(3)*4;f(3)f(2)*3;f(2)f(1)*2;f(1)1;递归出口每一步阶乘都是由上一次阶乘得来的即f ( n ) { f ( n − 1 ) × n , n 1 1 , n 1 f(n) \begin{cases} f(n-1)\times n, n1\\ 1, n1 \end{cases}f(n){f(n−1)×n,1,​n1n1​int fact(int n) { if (n 1) return 1; // 递归出口基线条件 return fact(n - 1) * n; // 递归调用 }时间复杂度 O(n)2.2斐波那契数列f ( n ) { 1 , n ≤ 2 f ( n − 1 ) f ( n − 2 ) , n 2 f(n) \begin{cases} 1, n\le 2\\ f(n-1)f(n-2), n2 \end{cases}f(n){1,f(n−1)f(n−2),​n≤2n2​2.2.1普通暴力递归O(2n)指数级但是这个递归规模非常大,呈爆炸式增长,呈现出树形结构 只能过去小范围n的 数据太大的话过不去 速度非常慢了 因为在递归的过程中 一个节点可能被递归了多次int fib(int n){ if(n2)return 1; return fib(n-1)fib(n-2); }2.2.2记忆化递归优化思想O(n)线性级通过标记递归过的数据 将统计过的数据记录下来 下次遇到相同问题时直接返回数据即可vectorint saved(n, -1);//保存计算结果 int fib(int n) { if (n 2) return 1; if (saved[n] -1) { saved[n] fib(n - 1) fib(n - 2); } return saved[n]; }2.3汉诺塔问题描述有三根柱子F(源)、A(辅助)、T目标)。A上有 n 个圆盘圆盘从上到下从小到大。规则一次只能移动 1 个盘子大圆盘永远不能放在小圆盘上面FFrom 源柱子AAux 辅助柱子TTo 目标柱子目标把全部 n 个盘子从 F 移动到T。递归思路把上面 n‑1 个盘子A → B借助 C 做辅助把最底下最大的 1 个盘子A → C直接移动把 B 上的 n‑1 个盘子B → C借助 A 做辅助基线条件n 1直接把盘子从源移到目标。数学递归式设H ( n ) H(n)H(n)为n个盘子需要移动的总次数H ( n ) { 1 , n 1 2 × H ( n − 1 ) 1 , n 1 H(n) \begin{cases} 1,n1\\ 2\times H(n-1)1,n1 \end{cases}H(n){1,2×H(n−1)1,​n1n1​通项公式H ( n ) 2 n − 1 \boldsymbol{H(n)2^n-1}H(n)2n−1n移动次数112337415531时间复杂度O(2n)指数爆炸n 不能取大void hanoi(int n, char F, char A, char T) { if (n 1) { printf(move %d from %c to %c\n, n, F, T); return; } hanoi(n - 1, F, T, A); printf(move %d from %c to %c\n, n, F, T); hanoi(n - 1, A, F, T); }3.如何编写递归函数3.1步骤确定参数(递归函数的参数 明确要解决什么问题参数代表当前子问题的规模)解决基准问题递归出口找到规模最小、可以直接算出答案的情况直接 return终止递归拆解问题 把大问题拆成一个或多个规模更小、形式相同的子问题调用自身求解子问题合并子问题结果。3.2递归本质:将问题拆解成更小规模的相同问题如果递归过程中存在大量重复子问题使用记忆化备忘录数组保存已经计算完成的结果避免重复递归降低时间复杂度。递归 自调用 拆分问题 回溯合并阶乘无重复递归 O(n)斐波那契朴素O(2n) → 记忆化O(n)汉诺塔天然指数递归无法优化xoei-1786602489322)]如果递归过程中存在大量重复子问题使用记忆化备忘录数组保存已经计算完成的结果避免重复递归降低时间复杂度。4.总结递归 自调用 拆分问题 回溯合并阶乘无重复递归 O(n)斐波那契朴素O(2n) → 记忆化O(n)汉诺塔天然指数递归无法优化重复计算优先使用记忆化搜索