第6章递归 6.1什么是递归 6.2递归调用的实现原理

一、栈 ( Stack ) 二、队列 ( Queue ) 三、递归的概念 四、递归与递归工作栈 五、递归与回溯

递归及其实现 递归算法在可计算性理论中占有重要地位,它是算法 设计的有力工具,对于拓展编程思路非常有用。就递 归算法而言并不涉及高深数学知识,只不过初学者要 建立起递归概念不十分容易。 我们先从一个最简单的例子导入

一、递归(Recurve)的概念 二、迷宫(Maze)问题 三、递归过程与递归工作栈 四、广义表(General Lists)

 归纳  数学归纳法  强数学归纳法  运用良序公理来证明  递归  递归定义  结构归纳法  递归算法

• 离散数学和计算机科学的关系 – 离散数学的特点、与计算机科学的关系 • 基本知识 – 偏序集合、最小上界、完全偏序集合、函数序、函数的单调性和连续性 • 递归函数的定义式的求解 – 函数的不动点、递归函数定义、递归函数定义的解、不动点算子、最小不动点定理 • 编程语言递归函数的数学语义

❖ 递归的实现机制 ❖ 递归算法编制 ❖ 递归关系式求解

 归纳： 数学归纳法与强数学归纳法 运用良序公理来证明  递归： 递归定义 结构归纳法与递归算法

递归的定义若一个对象部分地包含它 自己,或用它自己给自己定义,则称这 个对象是递归的;若一个过程直接地或 间接地调用自己,则称这个过程是递归 的过程

若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；而且一个过程直接地或间接地调用自己，则称这个过程是递归的过程