递归及递归算法 分析
1 递归及递归算法 分析
主要内容 递归的实现机制 递归算法编制 递归关系式求解
2 主要内容 ❖ 递归的实现机制 ❖ 递归算法编制 ❖ 递归关系式求解
递归的实现机制 1.递割归的概念 直接或间接地调用自身的算法称为递归算 法。 冬用函数自身给出定义的函数称为递归函数。 直接调用自身的算法称为直接递归 间接调用自身的算法称为间接递归
3 递归的实现机制 1.递归的概念 ❖ 直接或间接地调用自身的算法称为递归算 法。 ❖ 用函数自身给出定义的函数称为递归函数。 ❖ 直接调用自身的算法称为直接递归 ❖ 间接调用自身的算法称为间接递归
由分治法产生的子问题往往是原问题的较小 模式，这就为使用递归技术提供了方便。在 这种情况下，反复应用分治手段，可以使子 问题与原问题类型一致而其规模却不断缩小 最终使子问题缩小到很容易直接求出其解。 这自然导致递归过程的产生。 分治与递归像一对孪生兄弟， 经常同时应用 在算法设计之中，并由此产生许多高效算法
4 ❖ 由分治法产生的子问题往往是原问题的较小 模式，这就为使用递归技术提供了方便。在 这种情况下，反复应用分治手段，可以使子 问题与原问题类型一致而其规模却不断缩小， 最终使子问题缩小到很容易直接求出其解。 这自然导致递归过程的产生。 ❖ 分治与递归像一对孪生兄弟，经常同时应用 在算法设计之中，并由此产生许多高效算法
2.子程序的内部实现原理 。1)子程序调用的一般形式 一次调用N次调用嵌套调用 平行调用 主程序 主程序 主程序 主程序 子程序A 子程序A 子程序A 子程序A 子程序B call B 子程序B 2: call A call A 2: call A 1: call A call B 1: call A 1: 1: 2:
5 主程序 call A 1： 2.子程序的内部实现原理 ❖ 1）子程序调用的一般形式 一次调用 N次调用 嵌套调用 平行调用 子程序A 主程序 call A 1： call A 2： 子程序A 主程序 call A 1： 子程序A 子程序B call B 2： 主程序 call B 1： 子程序B call A 2： 子程序A