递归函数是什么递归函数是指在函数内部调用自身的函数。如果一个函数调用它本身那么这个函数就是递归的。递归思想把⼀个⼤型复杂问题层层转化为⼀个与原问题相似但规模较⼩的⼦问题来求解直到⼦问题不能再被拆分递归就结束了。所以递归的思考⽅式就是把大事化小的过程。递归中的递就是递推的意思归就是回归的意思至高理解我大学四年其实对递归都懵懵懂懂的我尝试过从很多个角度去理解递归。循环堆栈去理解模拟递归运算去理解都能想通但是始终就写不出。总缺少那么个阀点。当我大四考研的时候重新好好学习高数之后我发现计算机几乎所有层面都可以站在数学的角度去理解去思索。所以这次我要以数学去解决他。最最最重要的核心递归是数学归纳法在编程中的直接体现。数学归纳法递归函数证明 P(1) 成立写终止条件最小规模直接返回假设 P(k) 成立相信递归调用能解决子问题证明 P(k1) 成立用子问题的结果构造当前解常见误区这应该是初学时80%的朋友都有的误区这也是为什么要从数学上去理解。模拟视角我有点强迫症必须要脑子里面模拟递归过程才安心必须验证每一个阶段才行即使递归函数写出来了我能相信这个函数么。数学视角数学归纳法已经证明了只关心奠基和递推关系其他的归纳法都证明了不用关心细节。好好好你可能还是不直观。这个是心理上的问题就是你做数学题的时候代入函数计算等比等差公式记得把你知道首项和那个公差或者公比就可以直接用公式了压根就不会去模拟了对不对数学三步法写递归无论什么递归问题本质抓三个问题这也是递归的限制条件和思想的体现。按数学角度看就是以证明 12...n n(n1)/2 为例奠基最小规模的问题答案是什么比如 n 1 时等式成立。终止条件假设假设 n k 时成立递推证明 n k1 时也成立首先找终止条件最小规模的问题答案是什么这是终止条件最重要的一点如果递归没有终止条件就是个死循环。不需要递归一眼就能看出答案比如n 0 或 n 1 时直接返回什么if (n 0) return 0; if (n 1) return 1;然后是归纳假设假设函数能正确解决规模为 n-1或更小的子问题这是“数学信仰”不关心怎么算出来的就像你相信等差等比公式一样相信你的递归函数最后找递推关系如何用子问题的结果构造当前问题的解这是递归函数的“核心公式”找到f(n)和f(n-1)或f(n/2)等之间的数学关系return 子问题的结果 当前层要做的事;通用模板按上面三步法走可以总结出递归模板如下类型 函数名(参数) { // 结束条件 if (最简单的情况) { return 直接结果; } // 相信递归能搞定小一号的问题 类型 子结果 函数名(缩小后的参数); // 把小结果拼上当前这一步 return 子结果 当前层的处理; }行已经完成新手教程了直接挑战递归之王吧。递归之王汉诺塔问题有三根柱子A、B、CA柱上有 n 个大小不一的盘子大的在下小的在上。规则每次只能移动一个盘子大盘不能压在小盘上必须上小下大目标把 A 柱上的所有盘子移动到 C 柱可以借助 B 柱求打印出每一步的移动步骤思考A 柱上有 n 个的盘子大的在下小的在上。把A 柱上的所有盘子移动到 C 柱大盘不能压在小盘上。这说明不管怎么移动最后 A 柱下面那个最大的盘都要去到 C 柱下面。所以有下面的思考过程移动最大盘的时候C柱此时一定是空的才能把最大的放到C柱最下面。同时A柱上只能剩下这个最大盘。其他的所有盘一定在B柱上。而且说了大盘不能压在小盘上B盘上的也一定是大的在最下面。也就是说第一步要把上面那堆盘子从A柱挪到B柱上去。然后才能把最大盘从A柱移动到C柱。然后在想办法把B柱的盘子全部移动到C柱上也是小盘子压大盘子。经过上面这一轮后会发现原本A柱上的盘子除了最底下最大的盘子给了C柱其他盘子按着A柱原本的摆放顺序还是在B柱上。而始终是那三个柱子盘子还是那个从下到上的排列。唯一的区别就是A柱的盘子原封不动全部到B柱了除了最低下那个最大的移动到了C柱。说明后面的过程都是可以按每次移动最大的一块给C柱然后其他盘子还是原封不动给另一个柱。一样的方式只是盘子每次少了一个。接下来就是代码实现了就是代码模拟思维去实现他。上面的思考全是我的第一视角基于递归思想去一步一步推导的。步骤思考过程奠基n1 时只有一个盘子直接从 A 移到 C假设假设hanoi(n-1, ...)能正确把 n-1 个盘子从一根柱子移到另一根柱子递推1、把上面 n-1 个盘子从 A 移到 B借助 C2、把最大盘从 A 移到 C3、把 B 上的 n-1 个盘子移到 C借助 A代码示例#include stdio.h void move(char from, char to) { printf(%c - %c\n, from, to); } void hanoi(int n, char from, char aux, char to) { if (n 1) { move(from, to); return; } hanoi(n - 1, from, to, aux); // 把上面 n-1 个从 from 移到 aux借助 to move(from, to); // 把最大盘从 from 移到 to hanoi(n - 1, aux, from, to); // 把 aux 上的 n-1 个移到 to借助 from } int main() { int n; printf(请输入汉诺塔的层数: ); if (scanf(%d, n) ! 1 || n 0) { printf(输入无效请输入一个正整数。\n); return 1; } printf(移动步骤共 %d 步\n, (1 n) - 1); // 2^n - 1 步 hanoi(n, A, B, C); return 0; }