2009-7-25 1
第 5章 递归（ Recurve）
定义,若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；而且一个过程直接地或间接地调用自己，则称这个过程是递归的过程。
应用：
（ 1）用于某些概念的定义：
阶乘,if ( n>0 ) n ! = n ( n-1 ) !
if ( n=0 ) n ! = 1
单链表结点：
template <class Type> class ListNode
{private:
Type data;
ListNode<Type> * Link;
}
二叉树：二叉树是数据元素的有穷集合，它或者为空集（空二叉树），或者由一个根元素和其下的两棵互不相交的二叉树（左子树和右子树）构成。
2009-7-25 2
（ 2）用于编程
long f ( long n )
//求自然数 n 的阶乘 n !,n>=0
{ if ( n==0 ) return 1;
else return n * f ( n-1 );
}
递归算法的优点：易编程、可读性好、易检验可用归纳思维方法来理解和检验递归算法，但有一个基本条件和两个步骤：
基本条件：规格说明必须严格、精确地规定算法的功能、
入 / 出口信息、对外层量或全局量的影响步骤一：归纳基始 —— 验证算法对于最简单情况（递归出口）的正确性步骤二：由归纳假设进行归纳 —— 假设算法中的递归调用能正确实现规格说明之规定，然后验证整个算法能否实现规格说明之规定
2009-7-25 3
递归算法举例 —— 迷宫问题递归算法
void RecurveSeek ( int i,j )
//进入时 ( i,j )是一通道块，尚未印足迹，不在当前路径上。本函数
//从 ( i,j ) 起探索并输出以此时当前路径为前缀的所有成功的简单路
//径，退出时状态同进入时状态
{ maze[ i ] [ j ] = ‘0’ ; //印足迹，归入当前路径
if ( i == n && j == n ) printmaze( ) ; //简单情况
else for ( k = 0 ; k < 4 ; k ++ ) //试探东南西北四个方向
if ( maze[ i + di[ k ] ] [ j + dj[ k ] ] == ‘ ‘ ) //若下一块是通道
RecurveSeek( i + di[ k ],j + dj[ k ] ) ; //则递归调用
maze[ i,j ] = ‘ ‘ ; //回溯，恢复进入时状态
}
假定入口为 ( 0,0 ),则只需执行下列函数调用即可找到迷宫的所有简单路径：
RecurveSeek( 0,0 ) ;
2009-7-25 4
5.3 递归过程与递归工作栈为了保证递归调用的正确性，需要保存调用点的现场（返回地址、局部变量、被调用函数的参数等），以便正确地返回，并且按先进后出的原则来管理这些信息。在高级语言（编译程序）中，是通过利用“递归工作栈”来实现递归调用的。
f(n) f(n-1) f(n-2) f(1) f(0)
调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场
…
调用返回调用点
Pn Pn-1 Pn-2 P1 1
2009-7-25 5
计算 4 ! 递归过程图示：
下图中 Pi 代表现场信息，栈元素由现场信息和参数构成
f(4)=4*f(3) f(3)=3*f(2) f(2)=2*f(1) f(1)=1*f(0) f(0)=1
Push(e4) Push(e3) Push(e2) Push(e1)
f(4)= 4 * f(3) f(3)= 3 *f(2) f(2)= 2 *f(1) f(1)= 1 * f(0)
一般来说，递归方法的执行效率较低，但编程效率较高，因此常用来构建快速原型。另外递归结构一般可以转化成循环结构（有时需要栈操作的配合）。试实现上述阶乘计算的转化（要求用栈）。
P4 4
P3 3
P4 4
P2 2
P3 3
P4 4
P1 1
P2 2
P3 3
P4 4
Pop(e1)
Pop(e2)
Pop(e3)
Pop(e4)
2009-7-25 6
2009-7-25 7
第 5章 递归（ Recurve）
定义,若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；而且一个过程直接地或间接地调用自己，则称这个过程是递归的过程。
应用：
（ 1）用于某些概念的定义：
阶乘,if ( n>0 ) n ! = n ( n-1 ) !
if ( n=0 ) n ! = 1
单链表结点：
template <class Type> class ListNode
{private:
Type data;
ListNode<Type> * Link;
}
二叉树：二叉树是数据元素的有穷集合，它或者为空集（空二叉树），或者由一个根元素和其下的两棵互不相交的二叉树（左子树和右子树）构成。
2009-7-25 2
（ 2）用于编程
long f ( long n )
//求自然数 n 的阶乘 n !,n>=0
{ if ( n==0 ) return 1;
else return n * f ( n-1 );
}
递归算法的优点：易编程、可读性好、易检验可用归纳思维方法来理解和检验递归算法，但有一个基本条件和两个步骤：
基本条件：规格说明必须严格、精确地规定算法的功能、
入 / 出口信息、对外层量或全局量的影响步骤一：归纳基始 —— 验证算法对于最简单情况（递归出口）的正确性步骤二：由归纳假设进行归纳 —— 假设算法中的递归调用能正确实现规格说明之规定，然后验证整个算法能否实现规格说明之规定
2009-7-25 3
递归算法举例 —— 迷宫问题递归算法
void RecurveSeek ( int i,j )
//进入时 ( i,j )是一通道块，尚未印足迹，不在当前路径上。本函数
//从 ( i,j ) 起探索并输出以此时当前路径为前缀的所有成功的简单路
//径，退出时状态同进入时状态
{ maze[ i ] [ j ] = ‘0’ ; //印足迹，归入当前路径
if ( i == n && j == n ) printmaze( ) ; //简单情况
else for ( k = 0 ; k < 4 ; k ++ ) //试探东南西北四个方向
if ( maze[ i + di[ k ] ] [ j + dj[ k ] ] == ‘ ‘ ) //若下一块是通道
RecurveSeek( i + di[ k ],j + dj[ k ] ) ; //则递归调用
maze[ i,j ] = ‘ ‘ ; //回溯，恢复进入时状态
}
假定入口为 ( 0,0 ),则只需执行下列函数调用即可找到迷宫的所有简单路径：
RecurveSeek( 0,0 ) ;
2009-7-25 4
5.3 递归过程与递归工作栈为了保证递归调用的正确性，需要保存调用点的现场（返回地址、局部变量、被调用函数的参数等），以便正确地返回，并且按先进后出的原则来管理这些信息。在高级语言（编译程序）中，是通过利用“递归工作栈”来实现递归调用的。
f(n) f(n-1) f(n-2) f(1) f(0)
调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场
…
调用返回调用点
Pn Pn-1 Pn-2 P1 1
2009-7-25 5
计算 4 ! 递归过程图示：
下图中 Pi 代表现场信息，栈元素由现场信息和参数构成
f(4)=4*f(3) f(3)=3*f(2) f(2)=2*f(1) f(1)=1*f(0) f(0)=1
Push(e4) Push(e3) Push(e2) Push(e1)
f(4)= 4 * f(3) f(3)= 3 *f(2) f(2)= 2 *f(1) f(1)= 1 * f(0)
一般来说，递归方法的执行效率较低，但编程效率较高，因此常用来构建快速原型。另外递归结构一般可以转化成循环结构（有时需要栈操作的配合）。试实现上述阶乘计算的转化（要求用栈）。
P4 4
P3 3
P4 4
P2 2
P3 3
P4 4
P1 1
P2 2
P3 3
P4 4
Pop(e1)
Pop(e2)
Pop(e3)
Pop(e4)
2009-7-25 6
2009-7-25 7
