1 1栈、递归、树栈、递归、树1 递归基本概念2 用二叉树分析递归程序的执行过程3 递归程序的执行过程4 递归消除5 二叉树遍历的非递归算法栈、递归程序（递归算法）、二叉树和树的遍历有着紧密的联系，这一节，将就这些有关内容进行阐述2 21 递归基本概念递归基本概念递归在计算机科学和数学中是一个很重要的工递归在计算机科学和数学中是一个很重要的工具，它在程序设计语言中用来定义句法，在数具，它在程序设计语言中用来定义句法，在数据结构中用来解决表或树形结构的遍历和排序据结构中用来解决表或树形结构的遍历和排序等问题。数学家在研究组合问题时用到递归。等问题。数学家在研究组合问题时用到递归。递归是一个重要的课题，在计算方法、运筹学递归是一个重要的课题，在计算方法、运筹学模型、行为策略和图论研究中，从理论到实践，模型、行为策略和图论研究中，从理论到实践，都得到广泛的应用都得到广泛的应用3 3u定义定义：若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的，若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。u在以下三种情况下，常常要用到递归的方法数学函数的定义是递归的数学函数的定义是递归的数据结构是递归的数据结构是递归的问题的解法是递归的问题的解法是递归的( (分治的分治的) )从前有座山，山上有座庙，庙里有个老和尚，老和尚在从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事：从前有座山，讲故事：从前有座山，4 4u数学函数的定义是递归的数学函数的定义是递归的菲波那契函数菲波那契函数菲波那契函数菲波那契函数阿克曼函数阿克曼函数阿克曼函数阿克曼函数阶乘函数阶乘函数阶乘函数阶乘函数5 5u数据结构是递归的数据结构是递归的链表可以递归定义，链表使用递归定义，其算法链表可以递归定义，链表使用递归定义，其算法链表可以递归定义，链表使用递归定义，其算法链表可以递归定义，链表使用递归定义，其算法设计会比较简单设计会比较简单设计会比较简单设计会比较简单( (思考：如何对链表进行递归定义？如何设计递归算法思考：如何对链表进行递归定义？如何设计递归算法思考：如何对链表进行递归定义？如何设计递归算法思考：如何对链表进行递归定义？如何设计递归算法？) )树是递归定义的树是递归定义的树是递归定义的树是递归定义的6 6u问题的解法是递归的：有些问题用递归的方问题的解法是递归的：有些问题用递归的方法求解比较方便，典型的便子：法求解比较方便，典型的便子：hanoihanoi塔问题塔问题塔问题塔问题8 8皇后问题皇后问题皇后问题皇后问题迷宫问题迷宫问题迷宫问题迷宫问题快速排序、归并排序方法快速排序、归并排序方法快速排序、归并排序方法快速排序、归并排序方法树的遍历树的遍历树的遍历树的遍历7 7u递归问题特点递归问题特点对于一个较为复杂的问题，如果能够分解成几个对于一个较为复杂的问题，如果能够分解成几个相对简单的且解法相同或类似的子问题时，只要相对简单的且解法相同或类似的子问题时，只要解决了这些子问题，那么原问题就迎刃而解了，解决了这些子问题，那么原问题就迎刃而解了，这就是递归求解。这种分解这就是递归求解。这种分解-求解的策略叫做求解的策略叫做“分分治法治法”。当分解后的子问题可以直接解决时，就停止分解。当分解后的子问题可以直接解决时，就停止分解。我们把这些可以直接求解的问题叫做递归终止条我们把这些可以直接求解的问题叫做递归终止条件。件。任何递归问题都必须有递归终止条件任何递归问题都必须有递归终止条件。有些问题可以先设计出递归算法，然后为了提高有些问题可以先设计出递归算法，然后为了提高运行效率，再将递归算法变换成非递归算法运行效率，再将递归算法变换成非递归算法8 82. 用二叉树分析递归程序执行过程用二叉树分析递归程序执行过程#include int F(int n) int f,r;if(n=1) return 1; else r=F(n-1);f=n*r; return f; /main() y=F(5); coutn=n y=y;F(5)F(4)F(3)F(2)F(1)后序遍历后序遍历9 9#includevoid fun(int n,int *s) int f1,f2; if(n=1 | n=2)*s=1; else fun(n-1,&f1); fun(n-2,&f2); *s=2*f1+f2+1; coutf1tf2n; void main() int x; fun(4,&x); coutx=xendl;程序输出的第一行是程序输出的第一行是程序输出的第一行是程序输出的第一行是第二行是：第二行是：第二行是：第二行是：最后一行是：最后一行是：最后一行是：最后一行是：1,14,1x=10写出下列程序的输出结果写出下列程序的输出结果1010例 Hanoi问题(以3个盘子为例)BCA A A、B B、C C三个柱子，三个柱子，三个柱子，三个柱子，A A柱上有柱上有柱上有柱上有n n个大小个大小个大小个大小不一的盘子，盘子由大到小从下到上放不一的盘子，盘子由大到小从下到上放不一的盘子，盘子由大到小从下到上放不一的盘子，盘子由大到小从下到上放置，要求将置，要求将置，要求将置，要求将A A柱上的盘子移到柱上的盘子移到柱上的盘子移到柱上的盘子移到C C柱上，柱上，柱上，柱上，要求如下：要求如下：要求如下：要求如下：一次只能移动一只盘子；一次只能移动一只盘子；一次只能移动一只盘子；一次只能移动一只盘子；可以借助三根柱子，但任何时候都可以借助三根柱子，但任何时候都可以借助三根柱子，但任何时候都可以借助三根柱子，但任何时候都不允许大盘子在小盘子上面。不允许大盘子在小盘子上面。不允许大盘子在小盘子上面。不允许大盘子在小盘子上面。1111#include#includevoid move(int n,char x, char y)void move(int n,char x, char y) coutn:x coutn:xyendl;yendl; /void hanoi(int n,char A,char B,char C)void hanoi(int n,char A,char B,char C) if(n1) return ; if(n1) return ; else else hanoi(n-1,A,C,B); hanoi(n-1,A,C,B); move(n,A,C);move(n,A,C); hanoi(n-1,B,A,C);hanoi(n-1,B,A,C); void main()void main() int n; int n; coutinput plates number:; coutn; cinn; coutn; coutC2:A-B1:C-B3:A-C1:B-A2:B-C1:A-Cvoid hanoi(int n,char A,char B,char C)void hanoi(int n,char A,char B,char C) if(n1) return ; if(nC2:A-B1:C-B3:A-C1:B-A2:B-C1:A-C14143 递归算法递归算法u课后练习与讨论课后练习与讨论用递归方法实现单链表的基本操作用递归方法实现单链表的基本操作用递归方法实现单链表的基本操作用递归方法实现单链表的基本操作插入（创建）插入（创建）插入（创建）插入（创建）删除删除删除删除遍历遍历遍历遍历逆置逆置逆置逆置排序排序排序排序递归插入排序递归插入排序递归插入排序递归插入排序递归选择排序递归选择排序递归选择排序递归选择排序1515实现函数调作的基本设施栈实现函数调作的基本设施栈实现函数调作的基本设施栈实现函数调作的基本设施栈阶乘函数递归调用栈的变化阶乘函数递归调用栈的变化阶乘函数递归调用栈的变化阶乘函数递归调用栈的变化4 递归程序的执行过程递归程序的执行过程1616一般的函数调用一般的函数调用说明说明说明说明每调用函数一次，在内存栈区分配空间，用于存放函每调用函数一次，在内存栈区分配空间，用于存放函每调用函数一次，在内存栈区分配空间，用于存放函每调用函数一次，在内存栈区分配空间，用于存放函数数数数形式参数、局部形式参数、局部形式参数、局部形式参数、局部变量、返回值变量、返回值变量、返回值变量、返回值、返回地址、返回地址、返回地址、返回地址等信息等信息等信息等信息。intint f(intf(int x) x) intint y,zy,z; ; z=f1(y); z=f1(y); . . return(2*z); return(2*z); intint f1(int x) f1(int x) intint y,zy,z; ; z=f2(y); z=f2(y); . . return(2*z); return(2*z); intint f2(int t) f2(int t) intint a,ca,c; ; c=f3(a); c=f3(a); . . return(3+c); return(3+c); 1717参数参数参数参数局部变量局部变量局部变量局部变量返回值返回值返回值返回值返回地址返回地址返回地址返回地址参数参数参数参数局部变量局部变量局部变量局部变量返回值返回值返回值返回值返回地址返回地址返回地址返回地址参数参数参数参数局部变量局部变量局部变量局部变量返回值返回值返回值返回值返回地址返回地址返回地址返回地址参数参数参数参数局部变量局部变量局部变量局部变量返回值返回值返回值返回值返回地址返回地址返回地址返回地址mainmainf ff1f1f2f2toptop下一条要执下一条要执下一条要执下一条要执行的语句行的语句行的语句行的语句函数调用栈函数调用栈intint f(intf(int x) x) intint y,zy,z; ; z=f1(y); z=f1(y); . . return(2*z); return(2*z); intint f1(int x) f1(int x) intint y,zy,z; ; z=f2(y); z=f2(y); . . return(2*z); return(2*z); intint f2(int t) f2(int t) intint a,ca,c; ; c=f3(a); c=f3(a); . . return(3+c); return(3+c); 1818例例例例 求求求求n n的阶乘的阶乘的阶乘的阶乘( (取取取取 n=5)n=5)#include #include long long fac(intfac(int n) n) intint f; f;if(nif(n=1) =1) f=1;f=1; else else f=n*fac(n-1);f=n*fac(n-1); return (f); return (f); main()main() intint n, n, long y; long y; cincinn;n; y= y=factorial(nfactorial(n); ); coutcoutn=n y=y;n=n y=lchild;p=p-lchild;push(S,p);push(S,p);p=p-lchild;p=p-lchild;push(S,p);push(S,p);while(p)while(p) push(S,p); push(S,p); p=p-lchild; p=p-lchild; 2222ABCDEFGAACP=NULLBp pDDE EEGGGDF FFApop(S,p);pop(S,p);visit(p);visit(p);p=p-rchild;p=p-rchild;while(p)while(p) push(S,p); push(S,p); p=p-lchild; p=p-lchild; 2323p=T;p=T;push(S,P);push(S,P);p=lchild;p=lchild;push(S,p);push(S,p);p=p-lchild;p=p-lchild;push(S,p);push(S,p);while(p)while(p) push(S,p); push(S,p); p=p-lchild; p=p-lchild; pop(S,p);pop(S,p);visit(p);visit(p);p=p-rchild;p=p-rchild;while( ) p | StackEmpty()2424void void InorderTraverse(BiTreeInorderTraverse(BiTree T,(* T,(*visit)(ETypevisit)(EType e) e) IniStack(SIniStack(S);); p=T; p=T; while(pwhile(p | ! | ! StackEmpty(SStackEmpty(S) ) while(pwhile(p) /) /向左走到尽头向左走到尽头向左走到尽头向左走到尽头 push(S,ppush(S,p);); p=p- p=p-lchildlchild; ; pop(S,ppop(S,p););/空指针，退栈空指针，退栈空指针，退栈空指针，退栈 visit(pvisit(p););/处理节点处理节点处理节点处理节点 p=p-p=p-rchildrchild; ;/进入右分支进入右分支进入右分支进入右分支 中序遍历非递归算法中序遍历非递归算法2525void void PreorderTraverse(BiTreePreorderTraverse(BiTree T,(* T,(*visit)(ETypevisit)(EType e) e) IniStack(SIniStack(S);); p=T; p=T; while (p | ! while (p | ! StackEmpty(SStackEmpty(S) ) while(pwhile(p) /) /向左走到尽头向左走到尽头向左走到尽头向左走到尽头 visit(pvisit(p););/处理节点处理节点处理节点处理节点 push(S,ppush(S,p);); p=p- p=p-lchildlchild; ; pop(S,ppop(S,p););/空指针，退栈空指针，退栈空指针，退栈空指针，退栈 p=p-p=p-rchildrchild; ;/进入右分支进入右分支进入右分支进入右分支 前序遍历非递归算法前序遍历非递归算法2626void PostorderTraverse(BiTree T,(*visit)(EType e)IniStack(S); p=T; while(p | ! StackEmpty(S) while(p) /向左走到尽头向左走到尽头 push(S,p); p=p-lchild; q=NULL; flag=1; while(flag & ! StackEmpty(S) GetTop(S,p); if(p-rchild=q) /右子树为空或刚刚处理过右子树为空或刚刚处理过 pop(S,p); visit(p); q=p; else p=p-rchild; flag=0; /while后序遍历非递归算法后序遍历非递归算法2727另一种非递归遍历方法（数据结构定义）另一种非递归遍历方法（数据结构定义）TypedefTypedef enumbypassenumbypass=1,visit=0Tasktype=1,visit=0Tasktypestructstruct SlemSlem BtnodeBtnode *p; *p; TasktypeTasktype task; task;2828另一种非递归遍历方法（中序）另一种非递归遍历方法（中序）void InOrder_iter( BiTree BT) Elem e; Stack S(30); e.p=BT; e.task=bypass; / e为栈元素为栈元素 if(BT) Push(S, e); / 布置初始任务布置初始任务 while(!StackEmpty(S) / 每次处理一项任务每次处理一项任务 Pop(S,e); if(e.task=visit) visit(e.p); / 处理访问任务处理访问任务 else if(e.p) / 处理非空树的遍历任务处理非空树的遍历任务 p=e.p; e.p=p-rchild; e.task=bypass; Push(S,e); / 右孩子进栈右孩子进栈 e.p=p; e.task=visit; Push(S,e); /本节点（根）进栈本节点（根）进栈 e.p=p-lchild; e.task=bypass; Push(S,e);/左孩子进栈左孩子进栈 /if /while/InOrder_iter2929另一种非递归遍历方法另一种非递归遍历方法(前序前序)void PreOrder_iter( Btnode *BT) Slem e; Stack S(30); e.p=BT; e.task=bypass; / e为栈元素为栈元素 if(BT) Push(S, e); / 布置初始任务布置初始任务 while(!StackEmpty(S) / 每次处理一项任务每次处理一项任务 Pop(S,e); if(e.task=visit) visit(e.ptr); / 处理访问任务处理访问任务 else if(e.p) / 处理非空树的遍历任务处理非空树的遍历任务 p=e.p; e.p=p-rchild; e.task=bypass; Push(S,e); / 右孩子进栈右孩子进栈 e.p=p-lchild; e.task=bypass; Push(S,e); /左孩子进栈左孩子进栈 e.p=p; e.task=visit; Push(S,e); /根进栈根进栈 /if /while/InOrder_iter3030另一种非递归遍历方法另一种非递归遍历方法(后序后序)void PostOrder_iter( BiTree BT ) Slem e; Stack S(30); e.p=BT; e.task=bypass; / e为栈元素为栈元素 if(BT) Push(S, e); / 布置初始任务布置初始任务 while(!S.Empty(S) / 每次处理一项任务每次处理一项任务 Pop(S,e); if(e.task=visit) visit(e.ptr); / 处理访问任务处理访问任务 else if(e.p) / 处理非空树的遍历任务处理非空树的遍历任务 p=e.p; e.p=p; e.task=visit; Push(S,e); /根进栈根进栈 e.p=p-rchild; e.task=bypass; Push(S,e); /右孩子进栈右孩子进栈 e.p=p-lchild; e.task=bypass; Push(S,e); /左孩子进栈左孩子进栈 /if /while/InOrder_iter31316.5.4 递归消除递归消除u递归算法通常具有非常清晰的结构。而且大递归算法通常具有非常清晰的结构。而且大多数递归算法都具有超常的功能。善于阅读多数递归算法都具有超常的功能。善于阅读和设计递归算法对计算机科学和技术专业的和设计递归算法对计算机科学和技术专业的学生是至关重要的。学生是至关重要的。u有两个原因要研究递归算法的非递归化有两个原因要研究递归算法的非递归化对于递归算法往往其难理解其内部工作过程。对于递归算法往往其难理解其内部工作过程。对于递归算法往往其难理解其内部工作过程。对于递归算法往往其难理解其内部工作过程。递归算法的时间效率和空间效率往往都不尽人意递归算法的时间效率和空间效率往往都不尽人意递归算法的时间效率和空间效率往往都不尽人意递归算法的时间效率和空间效率往往都不尽人意递归程序的几种基本形式递归程序的几种基本形式尾递归消除方法尾递归消除方法一般递归消除方法一般递归消除方法3232递归程序的几种基本形式递归程序的几种基本形式int func() if(不满足递归终止条件不满足递归终止条件)func()u简单前序递归（尾递归）简单前序递归（尾递归）3333递归程序的几种基本形式递归程序的几种基本形式int func() if(不满足递归终止条件不满足递归终止条件)func() u简单后序递归简单后序递归3434递归程序的几种基本形式递归程序的几种基本形式intint funcfunc( () ) if(if(不满足递归终止条件不满足递归终止条件不满足递归终止条件不满足递归终止条件) ) funcfunc( () )funcfunc( () )u双重递归（前序）双重递归（前序）3535递归程序的几种基本形式递归程序的几种基本形式int func() if(不满足递归终止条件)func() func()u双重递归（中序）双重递归（中序）3636递归程序的几种基本形式递归程序的几种基本形式int func() if(不满足递归终止条件)func()func() u双重递归（后序）双重递归（后序）3737递归的本质递归的本质void func(p1,p2,pm) if(cond(p1,p2,pm) return ; else visit1(p1,p2,pm);func(f(p1,p2,pm);visit2(p1,p2,pm); while() visit1(); push() ; while( ) pop( ); vist2(); 3838递归的本质递归的本质void func(p1,p2,pm) if(cond(p1,p2,pm) return ;while(!cond(p1,p2,pm) visit1(p1,p2,pm); push(f(p1,p2,pm); while(!StackEmpty(S)pop(f(p1,p2,pm);visit2(p1,p2,pm); 3939简单前序递归（尾递归）消除简单前序递归（尾递归）消除intint funcfunc( () ) if(if(不满足递归终止条件不满足递归终止条件不满足递归终止条件不满足递归终止条件) )funcfunc( () )uu尾递归的递归调用语句只有尾递归的递归调用语句只有尾递归的递归调用语句只有尾递归的递归调用语句只有一个，而且是放在程序的最一个，而且是放在程序的最一个，而且是放在程序的最一个，而且是放在程序的最后。当递归调用返回时，返后。当递归调用返回时，返后。当递归调用返回时，返后。当递归调用返回时，返回到上一层递归调用语句的回到上一层递归调用语句的回到上一层递归调用语句的回到上一层递归调用语句的下一语句，这个位置正好是下一语句，这个位置正好是下一语句，这个位置正好是下一语句，这个位置正好是程序的末尾，因此，不必利程序的末尾，因此，不必利程序的末尾，因此，不必利程序的末尾，因此，不必利用递归工作栈保存返回地址，用递归工作栈保存返回地址，用递归工作栈保存返回地址，用递归工作栈保存返回地址，而且除了返回值和引用值外，而且除了返回值和引用值外，而且除了返回值和引用值外，而且除了返回值和引用值外，其它的参数和局部变量值都其它的参数和局部变量值都其它的参数和局部变量值都其它的参数和局部变量值都不再需要保留，因此可以不不再需要保留，因此可以不不再需要保留，因此可以不不再需要保留，因此可以不用栈，直接用循环形式写非用栈，直接用循环形式写非用栈，直接用循环形式写非用栈，直接用循环形式写非递归过程，从而提高程序的递归过程，从而提高程序的递归过程，从而提高程序的递归过程，从而提高程序的执行效率。执行效率。执行效率。执行效率。4040/尾递归循环实现尾递归循环实现尾递归循环实现尾递归循环实现void void recfun(intrecfun(int A,intA,int n)n) while (n=0) while (n=0) coutcoutAnAn-; n-; n-; /尾递归函数尾递归函数尾递归函数尾递归函数void void recfun(intrecfun(int A,intA,int n)n) if (n=0) if (n=0) coutcoutAnAn ; recfun(n-1); recfun(n-1); 4141简单后序递归简单后序递归intint funcfunc( () ) if(if(不满足递归终止条件不满足递归终止条件不满足递归终止条件不满足递归终止条件) )funcfunc( () ) u这种形式的递归程序要这种形式的递归程序要这种形式的递归程序要这种形式的递归程序要实现非递归化，一般来实现非递归化，一般来实现非递归化，一般来实现非递归化，一般来说要利用栈作辅助存储说要利用栈作辅助存储说要利用栈作辅助存储说要利用栈作辅助存储空间以保存上次调用的空间以保存上次调用的空间以保存上次调用的空间以保存上次调用的返回值、局部变量、返返回值、局部变量、返返回值、局部变量、返返回值、局部变量、返回地址等信息回地址等信息回地址等信息回地址等信息4242/递归程序递归程序递归程序递归程序void reverse()void reverse() char char chch; ; cin.get(chcin.get(ch);); if(chif(ch!=n)!=n) reverse(); reverse(); cout.put(chcout.put(ch);); /非递归程序非递归程序非递归程序非递归程序void reverse()void reverse() char char chch; ; InitStack(SInitStack(S);); cin.get(chcin.get(ch);); while(chwhile(ch!=n)!=n) push(S,chpush(S,ch);); cin.get(chcin.get(ch);); while(!StackEmpty(Swhile(!StackEmpty(S) pop(S,chpop(S,ch);); cout.put(chcout.put(ch);); 4343双重递归消除双重递归消除u联想联想双重递归的三种基本形式与二叉树三种递归遍历双重递归的三种基本形式与二叉树三种递归遍历双重递归的三种基本形式与二叉树三种递归遍历双重递归的三种基本形式与二叉树三种递归遍历之间的类比之间的类比之间的类比之间的类比