安阳做网站电话广州建设职业培训学校

安阳做网站电话,广州建设职业培训学校,重庆沙坪坝区房价,企业自助建站源码文章目录按调用“路数”分#xff08;最常见#xff09;按“谁调用谁”分按“调用的位置”分#xff08;性能优化向#xff09;总结递归是编程语言中常见的算法技巧#xff0c;但是递归名称很多#xff0c;我整理了一下递归常见的三种分类法。按调用“路数”分#xff0…文章目录按调用“路数”分最常见按“谁调用谁”分按“调用的位置”分性能优化向总结递归是编程语言中常见的算法技巧但是递归名称很多我整理了一下递归常见的三种分类法。按调用“路数”分最常见这是根据一个函数在递归时会派生出几个“分身”来分类的。A. 线性递归 (Linear Recursion)特点函数在递归阶段只调用一次自己。长相voidlinear(int n){if(n0)return;// 只调用一次自己linear(n-1);}理解这就像是一个单向链表或者一根绳子一头拉着一头直到拉断触底反弹。例子计算阶乘、遍历单链表。优化这种递归可以直接改成循环B. 树形递归 (Tree Recursion)*特点函数在递归阶段调用了多次通常是两次或以上自己。*长相voidtree(int n){if(n1)return;// 调用两次自己这就分叉了tree(n-1);tree(n-2);}理解这就像是二叉树的遍历每走一步就分两叉呈指数级爆炸增长。例子斐波那契数列朴素写法、二叉树遍历。优化这种递归有两种优化方案使用显式栈避免系统栈溢出和记忆化搜索加缓存。但是要视情况而定显式栈代码复杂而多线程环境里的fork/join用的树形递归往往是拆分数据集几乎没有重复的入参加缓存没有用。按“谁调用谁”分这是根据函数调用的“人际关系”来分类的。A. 直接递归 (Direct Recursion)特点函数A直接调用自己(A)。长相voidA(){// ...A();// 我直接call我自己}备注这是我们最最常用的递归方式。B. 间接递归 (Indirect Recursion)特点函数A调用函数B函数B又反过来调用函数A。长相voidA(){// ...B();// 我让兄弟帮我干}voidB(){// ...A();// 兄弟又把活扔回给我}理解这就像是两个人互相踢皮球直到把球踢烂栈溢出或者达成条件停止。按“调用的位置”分性能优化向这是你提到的尾递归所在的分类也是性能优化的关键。A. 头递归 (Head Recursion)特点先递归调用拿到结果后再进行计算或者说递归调用在函数体的前面。长相inthead(int n){if(n0)return0;// 先递归下去等回来之后还要做 n 的操作returnhead(n-1)n;}缺点必须把每一层的现场比如这里的 n都保存在栈里等着“归”的时候用。容易栈溢出。B. 尾递归 (Tail Recursion) —— 你提到的那位特点递归调用是函数的最后一步操作。调用之后函数不需要再做任何计算了直接返回结果就行。长相inttail(int n,int acc){if(n0)returnacc;// 计算已经在参数里做完了(acc n)这里只是单纯的跳转returntail(n-1,accn);}优点编译器可以进行尾调用优化 (TCO)。它不需要保留上一层的栈帧直接把当前栈覆盖掉就行。这样无论递归多少层栈空间永远是 O(1) 的不会栈溢出。总结分类维度类型关键特征调用路数线性递归一层只调一次自己树形递归一层调多次自己调用关系直接递归自己调自己间接递归你调我我调你调用位置头递归调完还要算尾递归调完直接返