C语言递归函数笔记（函数自己调自己）

一、什么是递归递归 就是一个函数在它自己的定义里 调用它自己。有点像俄罗斯套娃或者镜子里的镜子。最简单的例子虽然是无限递归别真跑cvoidinfinity(){printf(again\n);infinity();// 自己叫自己}没有停止条件会一直调直到栈爆掉。二、递归的两个必要条件终止条件基例什么时候不再递归直接返回结果。递归步骤把大问题拆成更小的同类问题不断逼近终止条件。三、经典例子阶乘数学定义0!1n!n*(n-1)!n0写成递归cintfactorial(intn){if(n1)return1;// 终止条件elsereturnn*factorial(n-1);// 递归n! n * (n-1)!}调用 factorial(3) 时发生了什么textfactorial(3)-3*factorial(2)factorial(2)-2*factorial(1)factorial(1)-1返回1 - 2 - 6先一层层往下递到底了再一层层往回归所以叫“递归”。四、栈的作用回顾一下每次函数调用系统会在 栈 上分配一个 栈帧用来存参数局部变量返回地址之后要回到哪里递归调用时每深入一层就新建一个栈帧返回时再逐层销毁。画个图n3text main 调用factorial(3) 栈底[main][factorial(3)参数3,返回地址main...][factorial(2)参数2][factorial(1)参数1]栈顶返回来时从顶往下弹。所以递归太深会 栈溢出Stack Overflow就是栈帧太多把栈空间占满了。五、经典例子斐波那契数列定义fib(0)0, fib(1)1, fib(n)fib(n-1)fib(n-2)cintfib(intn){if(n0)return0;if(n1)return1;returnfib(n-1)fib(n-2);}问题是效率极低重复计算太多。比如 fib(5) 要算textfib(5)/\fib(4)fib(3)/\/\fib(3)fib(2)fib(2)fib(1)/\/\/\fib(2)fib(1)...很多节点重复计算。fib(40) 就能跑到几亿次调用卡死你。优化方法记忆化把算过的存起来或用循环。六、递归 vs 循环方面 递归 循环代码简洁性 某些问题极简树、汉诺塔 一般代码量略多效率 有函数调用开销 快内存 每层占栈空间 只需几个变量风险 容易栈溢出 一般不会适合场景 问题本身就是递归定义文件目录、树、图 大部分普通迭代经验能用循环就别用递归除非递归写起来明显清晰很多且深度不会太大。七、尾递归能优化的递归尾递归递归调用是函数的 最后一步操作之后没有其他计算。阶乘通常写法不是尾递归因为要 n * factorial(n-1)乘号在递归返回之后才做。改成尾递归cintfactorial_tail(intn,intacc){if(n1)returnacc;returnfactorial_tail(n-1,n*acc);}// 调用factorial_tail(5, 1)尾递归的好处是某些编译器可以优化成循环不再新建栈帧省内存。但很多C编译器不自动做尾递归优化需要开优化选项权当了解一下。八、经典的递归例子练手用字符串反转递归版cvoidreverse(char*s){if(*s\0)return;reverse(s1);putchar(*s);}// 输入abc输出cba汉诺塔cvoidhanoi(intn,charfrom,charto,charaux){if(n1){printf(Move disk 1 from %c to %c\n,from,to);return;}hanoi(n-1,from,aux,to);printf(Move disk %d from %c to %c\n,n,from,to);hanoi(n-1,aux,to,from);}遍历二叉树数据结构里会学cvoidinorder(TreeNode*root){if(!root)return;inorder(root-left);printf(%d ,root-val);inorder(root-right);}九、常见坑和调试建议没有终止条件或条件永远达不到→ 无限递归 → 栈溢出崩掉。递归深度太大比如 fib(100000) 直接炸。一般栈空间默认约1~8MB深度几百到几千就可能崩看参数大小。重复计算像斐波那契那样加个缓存数组存中间结果。返回局部变量地址与递归无关但容易犯int* bad() { int x5; return x; } 返回栈地址。调试递归可以加个缩进参数打印每次进入和退出方便看调用顺序。cvoiddebug_fact(intn,intdepth){for(inti0;idepth;i)printf( );printf(fact(%d)\n,n);if(n1)return;debug_fact(n-1,depth1);}十、什么时候该用递归问题本身是递归结构文件系统目录树、JSON/XML解析、递归下降解析器。分治算法快速排序、归并排序虽然递归也有限制但深度logN安全。动态规划有时递归记忆化更直观。写一些面试题比如逆序打印字符串。十一、总结背几句就行递归 自己调用自己 终止条件。每层调用消耗栈空间太深会崩。递归能写得很简短但往往不如循环高效。写递归前先想怎么把问题变小什么时候停下来。调试时可以从小的输入开始比如n1,2,3手动模拟一下。多写几个递归函数比如求最大公约数辗转相除法、数的二进制表示、判断回文字符串练多了就自然了。递归就像剥洋葱一层一层剥到心再往回包。