第一章 递归(recursion)

• ​3.递归过程的实现

  • ​调用分类

    • ​内部调用

    • ​外部调用

  • ​工作记录

    • ​本次递归调用中的局部变量

    • ​返回地址

    • ​与形参结合的实参值

      • ​函数名

      • ​引用参数

      • ​数值参数

  • ​递归工作栈

    • ​解决问题

      • ​参数传递

      • ​返回地址

    • ​调用【保存现场】：建立工作记录；入栈；

    • ​返回【恢复现场】：弹出工作记录；出栈；

• ​1.递归的概念

  • ​定义

    • ​递归的对象

      • ​部分地包含自身

      • ​利用自身定义自身

    • ​递归过程

      • ​直接或间接地调用自身

  • ​分类

    • ​直接递归

    • ​间接递归

  • ​方法论

    • ​从简单到复杂

    • ​从低级到高级

• ​2.基本递归过程

  • ​递归求解的过程

    • 递归调用：分解后​分治求解

    • ​递归终止条件（递归出口）：直接求解

  • ​适用情况

    • ​问题的定义是递归的

    • ​问题涉及的数据结构是递归的

    • ​问题解法满足递归性质

• ​4.递归效率

  • ​限制原因

    • 函数调用

    • ​参数传递

  • ​尾递归：唯一的递归调用是函数的最后一个动作

  • ​替代：循环或迭代