网站建设课程设计实训心得,长沙做营销型网站公司,花都网站制作公司,wordpress文章如何分类添加目录
第一步#xff1a;❓我们要解决什么#xff1f;
第二步#xff1a;将其类比为求自然数和
第三步#xff1a;什么是每一项#xff1f;
第四步#xff1a;定义要计算的每一项#xff08;term#xff09;
第五步#xff1a;定义递归函数结构 #x1f333; 调用…目录
第一步❓我们要解决什么
第二步将其类比为求自然数和
第三步什么是每一项
第四步定义要计算的每一项term
第五步定义递归函数结构 调用树结构
完整代码
复杂度分析 总结图从定义到实现 我们将用第一性原理来一步一步推导如何用 C 实现泰勒展开式Taylor Series Expansion并借助递归求自然数之和的思想进行类比和迁移。
第一步❓我们要解决什么
我们要用 C 写一个函数计算 e^x 的近似值基于泰勒展开公式。 第二步将其类比为求自然数和
你已经知道
int sumOfNumbers(int n)
{if (n 0)return 0;elsereturn sumOfNumbers(n - 1) n;
}
我们同样可以将泰勒级数看作是
f(x) 第0项 第1项 第2项 … 第n项所以我们可以尝试用递归方法去表达每一项累加所有项。
第三步什么是每一项
我们先思考“泰勒展开”的一项的数学结构 我们从第一性原理推导出这个公式的两部分组成 分子是 x^n也就是 x * x * x……共n次 分母是 n!n * (n−1) * (n−2)⋯1
所以我们必须做两件事 每次递归都乘一次 x → 累计分子 每次递归都乘一次当前 n → 累计分母
从递归角度重新理解
如果你在写一个 taylor(n) 递归函数你会每次调用去表示 我要计算第 n 项 第 n 项是第 n−1 项 * x / n
于是我们可以这样递推 ✅ 这个推导说明
我们不需要单独重复计算 x^n 和 n
我们可以利用上一步的结果乘一个新的因子 x / n 就能得到下一项。 第四步定义要计算的每一项term
❓问题来了
如果我们想用递归函数一步一步计算
double taylor(int n, double x);那么问题是 上一项计算的结果在哪里 本层计算需要的 x^(n-1) 和 n-1!怎么得来
直觉尝试用返回值传信息
你可能会尝试每次都重新计算 x^n 和 n!像这样
double taylor(int n, double x) {return taylor(n-1, x) pow(x, n) / factorial(n); // NOT efficient
}问题 每一层都重复算一遍幂和阶乘 没有重用信息
✅ 真正的优化思路我们需要“带状态的递归”
我们希望每次调用都记住前一项计算中积累出来的 x^n 和 n!
于是我们可以 在函数内部保留静态变量或全局变量 让它在每一层递归中不断更新
我们引入三个全局变量
double num 1; // 分子x^n
double den 1; // 分母n!每次递归做的事情就是 分子幂函数乘上 x 分母阶乘乘上 n 计算这一项 term num / den 递归进入下一层直到 n 0 为止
为什么不用局部变量 每一层递归函数自己的局部变量在返回时会销毁状态无法累积。 静态/全局变量可以在整个递归调用链中持续保存状态。
第五步定义递归函数结构
我们遵循 先处理“底部终止条件”n 0 然后递归地构造前一项的和 最后处理当前这一项的贡献
否则你将会提早计算当前项还没到你这一层状态错位。
Step 1递归函数要怎么“停下来”
在定义任何递归函数的时候必须先回答一个问题
✨ 什么时候这个函数应该“终止”不再递归
这就是我们要设定的base case基础情况。
在泰勒展开中第 0 项是已知的常数 1所以我们在 n0 时应该返回1
if (n 0) return 1;✅ 这是递归的“锚点”你必须先写否则递归会无限下去。
Step 2递归要先“构造前面的和”
✨思维实验
假设你现在写的是
double taylor(int n, double x) {num * x;den * n;double res taylor(n - 1, x);return res num / den;
}你发现问题了没
你先更新了 num 和 den然后才去计算上一项的结果这就打乱了状态的对应关系——因为上一
项本来是 x^(n-1) / (x-1) !但你已经把它提前变成 x^n / x ! 了。
错误我们在进入上一个递归之前就已经变更了状态
✅ 正确方式
我们应该 先去计算 上一项的累加和taylor(n - 1) 回来以后再更新状态 然后把当前这一项加进去
double taylor(int n, double x) {if (n 0) return 1;double res taylor(n - 1, x); // 先去处理前面项num * x; // ⏪回来再乘 xden * n; // ⏪回来再乘 nreturn res num / den; // ⏫最后加上当前这一项
}注意这是典型的“递归先深入到底部递归树的叶子”然后在回溯的过程中逐层累计每一项。 调用树结构
示例调用 taylor(3, x)即展开 4 项 (n3)
我们每调用一次函数都画出一层并在返回时说明计算了哪一项。 taylor(3)↓taylor(2)↓taylor(1)↓taylor(0) ← base case 1然后回溯计算从下向上 返回 taylor(0) 1 回到 taylor(1) 分子 num * x → x 分母 den * 1 → 1 加项 x^1/1! x 回到 taylor(2) num * x → x² den * 2 → 2 加项 x^2 / 2! 回到 taylor(3) num * x → x³ den * 3 → 6 加项 x^3 / 3!
taylor(0) 1
taylor(1) taylor(0) x / 1
taylor(2) taylor(1) x^2 / 2
taylor(3) taylor(2) x^3 / 6回溯顺序
taylor(1) ← x^1 / 1! ← 分子: x分母: 1
taylor(2) ← x^2 / 2! ← 分子: x²分母: 2
taylor(3) ← x^3 / 3! ← 分子: x³分母: 6你看到没正是因为我们在回溯阶段才处理当前项才确保每一项都在它该在的位置
调用层n分子num分母den当前项 33x^33 !6x^3 / 622x^22 !2x^2 / 211x1 !1x/1001初始值1初始值1
完整代码
double num 1; // 分子
double den 1; // 分母double taylor(int n, double x) {if (n 0) return 1; // 1️⃣ 锚点停止递归double res taylor(n - 1, x); // 2️⃣ 先构造前面所有项的和num * x; // 3️⃣ 然后再更新状态den * n;return res num / den; // 4️⃣ 当前项加进去
}复杂度分析
这是一个非常经典的线性递归linear recursion结构。我们来详细分析其时间复杂度和空间复杂度。
⏱️时间复杂度分析Time Complexity
我们从函数调用过程来看 调用 taylor(n) 会递归调用 taylor(n-1) taylor(n-1) 又会调用 taylor(n-2) ... 最后到底部 taylor(0) 返回 1然后逐层回溯
整个递归链条是
taylor(n)→ taylor(n-1)→ taylor(n-2)...→ taylor(0)总共会调用 n1 次函数从 0 到 n。
每一层递归执行的是 一个函数调用taylor(n - 1) 两次乘法num * x, den * n 一次加法res num / den
这些操作都是常数时间 O(1)。 ✅ 所以时间复杂度为On
空间复杂度分析Space Complexity
这就有趣了因为这是递归。
你没有使用堆内存比如数组、链表但递归函数本身会在调用栈上分配帧 每调用一次 taylor(n)系统会开辟一块栈帧来保存 参数 n, x 局部变量 res 返回地址
由于这个是线性递归不是尾递归函数不会在递归过程中被优化掉除非特别启用尾递归优化C 一般不保证。 ✅ 所以空间复杂度为On 总结图从定义到实现
数学定义term_n x^n / n! ← 每一项都能用前一项 * (x/n) 得到递归目标taylor(n) taylor(n-1) term_n中间状态num ← num * xden ← den * n于是代码num 1;den 1;double taylor(n, x) {if n0 return 1;res taylor(n-1, x);num * x; den * n;return res num / den;}
