3.3.3 栈在递归中的应用

教材导航 · 第3章

原书定位

印刷页P92起,对应PDF第104页。下文为目视整理的知识提要;完整内容见原书对照。

每层函数调用保存参数、局部变量、返回地址等信息,返回时按后进先出恢复。递归需要规模减小的递归体与可达的出口条件;空间复杂度按最大同时存在的调用层数计算。

递归可改成显式栈模拟,也可能通过迭代或公式消除栈。递归本身不必然低效,重复子问题会增加时间;斐波那契朴素递归就是典型例子。遍历树等问题的递归层数与树高有关。

图3.16 斐波那契递归调用树

图3.16 斐波那契递归调用树,原书P93。

对应练习

3.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P92,PDF第104页

原书对照,原书P93,PDF第105页