递归函数是什么
递归函数是指在函数内部调用自身的函数。如果一个函数调用它本身，那么这个函数就是递归的。
递归思想
把⼀个⼤型复杂问题层层转化为⼀个与原问题相似，但规模较⼩的⼦问题来求解；直到⼦问题不能再被拆分，递归就结束了。所以递归的思考⽅式就是把大事化小的过程。
递归中的递就是递推的意思，归就是回归的意思
至高理解
我大学四年其实对递归都懵懵懂懂的，我尝试过从很多个角度去理解递归。循环堆栈去理解，模拟递归运算去理解，都能想通但是始终就写不出。总缺少那么个阀点。
当我大四考研的时候重新好好学习高数之后，我发现计算机几乎所有层面都可以站在数学的角度去理解，去思索。所以这次我要以数学去解决他。
最最最重要的核心：递归是数学归纳法在编程中的直接体现。
| 数学归纳法 | 递归函数 |
|---|---|
| 证明 P(1) 成立 | 写终止条件（最小规模直接返回） |
| 假设 P(k) 成立 | 相信递归调用能解决子问题 |
| 证明 P(k+1) 成立 | 用子问题的结果构造当前解 |
常见误区
这应该是初学时80%的朋友都有的误区，这也是为什么要从数学上去理解。
模拟视角：我有点强迫症，必须要脑子里面模拟递归过程，才安心，必须验证每一个阶段才行，即使递归函数写出来了，我能相信这个函数么。
数学视角：数学归纳法已经证明了，只关心奠基和递推关系，其他的归纳法都证明了，不用关心细节。好好好你可能还是不直观。
这个是心理上的问题，就是你做数学题的时候代入函数计算，等比等差公式记得把，你知道首项和那个公差或者公比，就可以直接用公式了，压根就不会去模拟了对不对！
数学三步法写递归
无论什么递归问题，本质抓三个问题，这也是递归的限制条件和思想的体现。
按数学角度看就是：（以证明 1+2+...+n = n(n+1)/2 为例）
奠基：最小规模的问题，答案是什么？；比如 n = 1 时，等式成立。（终止条件）
假设：假设 n = k 时成立
递推：证明 n = k+1 时也成立
首先找终止条件
最小规模的问题，答案是什么？这是终止条件最重要的一点，如果递归没有终止条件，就是个死循环。
不需要递归，一眼就能看出答案；比如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、C），A柱上有 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柱，然后其他盘子还是原封不动给另一个柱。一样的方式，只是盘子每次少了一个。
接下来就是代码实现了，就是代码模拟思维去实现他。上面的思考全是我的第一视角基于递归思想去一步一步推导的。
| 步骤 | 思考过程 |
|---|---|
| 奠基 | n=1 时，只有一个盘子，直接从 A 移到 C |
| 假设 | 假设hanoi(n-1, ...)能正确把 n-1 个盘子从一根柱子移到另一根柱子 |
| 递推 | 1、把上面 n-1 个盘子从 A 移到 B（借助 C） 2、把最大盘从 A 移到 C 3、把 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; }
