栈在递归中的应用

文章目录递归三要素底层机制栈的应用递归三要素递归表达式递推关系如何把大问题拆成小问题。例如Fact(n) n * Fact(n-1)。边界条件递归出口何时不再调用自身。例如if(n1) return 1;。向终止条件递推每次递归调用都向终止条件靠近如n逐渐减小到1。递归本质函数自己调用自己每一次递归调用都会生成新栈帧压入系统栈函数执行完毕栈帧出栈。完美契合栈LIFO 后进先出最后调用的函数最先执行完毕返回。适合用递归算法解决可以把原始问题转换为属性相同但规模较小的问题。底层机制栈的应用函数调用的特点最后被调用的函数最先执行结束LIFO每次函数调用时需要一个“函数调用栈”存储函数返回地址调用结束回到上一层代码要执行的位置实参局部变量区分系统栈运行时自动维护我们自己代码写的栈是用户自定义栈。递归使用系统栈递归转非递归需要手动模拟、使用自定义栈。递归调用时函数调用栈可称为“递归工作栈”每进入一层递归就将递归调用所需信息压入栈顶每退出一层递归就从栈顶弹出相应信息当每一次函数调用结束之后就弹出栈递归的缺点效率低太多层递归可能会导致栈溢出可能包含很多重复计算。可以自定义栈将递归算法改造成非递归算法。