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