递归与非递归程序的转换.ppt

1、递归程序非递归程序,张仕 ,0 递归的基本概念,递归：在定义一个过程或函数时，如果出现调用本过程或本函数的成分，则称为递归。 直接递归：在定义一个过程或函数时，出现直接调用本过程或本函数成分的情况。 直接递归：在定义一个过程或函数时，出现间接调用本过程或本函数成分的情况。,0 递归的基本概念,function_1(X) if( X) X*function_1(X-1); else return; Function_1、function_2实现了什么功能？ 还有哪些常见的递归函数？,function_2(X) if( X) function_3(X); else return; function

2、_3(X) return X*function_2(X-1); ,0 递归的基本概念,在什么情况下用到递归方法 给出的定义是递归的：许多数学公式、数列的定义是递归的，这是可以直接把递归定义转换为递归算法：例如Fabonacci数列。 数据结构是递归的：常见的有树、链表等数据结构的定义。对于这类数据结构，常采用递归的方法进行操作。例如链表的遍历、树的遍历操作。 问题求解的方法是递归的。例如汉诺塔问题，其求解方法是递归的。,1 递归算法的设计,递归模型：递归模型是递归算法的抽象,它反映递归问题的递归结构,例如,前面的递归算法对应的递归模型如下： fun(0)=1 n=0(1) fun(n)=n*f

3、un(n-1)n0(2) 其中：第一个式子给出了递归的终止条件,我们称之为递归出口；第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系，我们称之为递归体。,1 递归算法的设计,一般地,一个递归模型是由递归出口和递归体两部分组成, 前者确定递归到何时结束, 后者确定递归求解时的递推关系。 递归出口的一般格式如下： f(s1)=m1 这里的s1与m1均为常量,有些递归问题可能有几个递归出口。,1 递归算法的设计,递归体的一般格式如下： f(sn+1)=g(f(si),f(si+1),f(sn),cj,cj+1,cm) 其中, n,i,j,m均为正整数。 sn+1是一个递归“大问题”,

4、 si,si+1,sn为递归“小问题”, cj,cj+1,cm是可以用非递归方法直接解决的问题 g是一个非递归函数,可以直接求值。,1 递归算法的设计,递归思路 实际上，递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决(此时分解到递归出口)。 但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似。并且有一个分解的终点。从而使问题可解。,1 递归算法的设计,逐步分解和组合求值的过程,1 递归算法的设计,斐波那契数：一个大问题分解为多

5、个小问题的过程,1 递归算法的设计,算法设计：先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。 而这些子问题具有与原问题相同的求解方法，于是可以再将它们划分成若干个子问题，分别求解，如此反复进行，直到不能再划分成子问题，或已经可以求解为止。 这种自上而下将问题分解、求解，再自上而下引用、合并，求出最后解答的过程称为递归求解过程。 这是一种分而治之的算法设计方法。,1 递归算法的设计,递归设计的步骤如下： (1)对原问题f(s)进行分析,假设出合理的“较小问题”f(s)(与数学归纳法中假设n=k-1时等式成立相似)； (2)假设f(s)是可解的,在此基础上确定f(s)的

6、解,即给出f(s)与f(s)之间的关系(与数学归纳法中求证n=k时等式成立的过程相似)； (3)确定一个特定情况(如f(1)或f(0)的解,由此作为递归出口(与数学归纳法中求证n=1时等式成立相似)。,1 递归算法的设计,课堂练习： 采用递归算法求实数数组A0.n-1中的最小值。 基本步骤： 先定义清楚问题； 写出递归模型； 转换为算法。,2 为什么：递归非递归？,引例 求如下函数值 Sum(1.X)=X+Sum(1.X-1) X0 Sum(1.X)=0 X=0 它的程序？,2 为什么：递归非递归？,利用递归求该函数 #include stdafx.h #include using names

7、pace std; int _tmain(int argc, _TCHAR* argv) coutadd(5000); return 0; ,int add(int x) if(x=0) return 0; return x+add(x-1); ,2 为什么：递归非递归？,利用非递归(迭代)求该函数 #include stdafx.h #include using namespace std; int _tmain(int argc, _TCHAR* argv) coutsum(5000); return 0; ,int sum(int x) int result=0; for(int i=x

8、; i0; i-) result+=x; return result; ,2 为什么：递归非递归？,它们的运行结果？ 递归 迭代 X=10 X=100 X=1000 X=10000 X=100000 为什么？,2 为什么：递归非递归？,利用递归求该函数 #include stdafx.h #include using namespace std; int _tmain(int argc, _TCHAR* argv) coutadd(5000); return 0; ,int add(int x) char a1000; if(x=0) return 0; return x+add(x-1);

9、,2 为什么：递归非递归？,递归的原理？ 为什么要使用非递归？（内存、效率） 递归和非递归的优缺点？ 什么时候使用递归？,3 递归非递归的转换,把递归算法转化为非递归算法有如下三种基本方法： (1)自己用栈模拟系统的运行时栈，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法。 (2)利用栈保存参数，由于栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法。 (3)通过分析，跳过分解过程，直接用循环结构的算法实现求值过程。,3 递归非递归的转换方法1-表述1,求 解 过 程,3 递归非递归的转换方法1-表述1,自定义堆栈法：采用自定义堆栈替代系统堆栈的方式实现递归函

10、数的转换。 目的：为不能分析出来循环的递归操作提供开销可控的方法。 适用性：所有的递归函数。 如何实现？,3 递归非递归的转换方法1-表述1,基本思想（详细见2-1-1.cpp）： 递归中函数的每一层都两次到达，一次是继续往下一层递归，另外下一层的递归出来后。两次要做的工作是不一样的。 1 进入某一程序时，需要做一些预备工作； 2 进行递归调用，进入下一层； 3 下一层返回，利用返回结果组合出新的结果。,3 递归非递归的转换方法1-表述1,练习： 1 求N！的递归算法； 2 求N！的栈模拟递归算法； 3 求斐波那契数的递归算法； 4 求斐波那契数的栈模拟递归算法。 其中，斐波那契数（Foban

11、acci）定义如下： f(1)=1 f(2)=1 f(n)=f(n-1)+f(n-2),其中n=2,讨论直接使用栈保存中间结果，从而将递归算法转化为非递归算法的过程。以求N!为例,其递归模型有一个递归体和一个递归出口两个式子,分别称为(1)式和(2)式。,3 递归非递归的转换方法1-表述2,设计一个栈,其结构如下： struct int vn; /*保存n值*/ int vf; /*保存fun1(n)值*/ int tag; /*标识是否求出fun1(n)值, 1:未求出,0:已求出*/ StMaxSize;/*定义简单数组栈*/,3 递归非递归的转换方法1-表述2,计算fun1(5)之值的过

12、程如下： 将(5,*,1)进栈; while (栈不空) if (未计算出栈顶元素的vf值即Sttop.tag=1) if (栈顶元素满足(1)式) 求出对应的Sttop.vf值, 置Sttop.tag=0; else /*栈顶元素满足(2)式*/ 将(Sttop.vn-1,*,1)进栈; else if (已计算出栈顶元素的vf值即Sttop.tag=0) 显然栈顶元素由次栈顶元素通过(2)式分解得到的，回过来 由栈顶元素的vf值计算出次栈顶元素的vf值并退栈; if (栈中只有一个已求出vf值的元素) 退出循环; St0.vf即为所求的fun1(n)值;,3 递归非递归的转换方法1-表述2

13、,3 递归非递归的转换方法1-表述2,对应的非递归fun1算法如下： int fun1(int n) top+; /*初值进栈*/ Sttop.vn=n; Sttop.tag=1; while (top-1) /*栈不空时循环*/ if (Sttop.tag=1) /*未计算出栈顶元素的vf值*/ if (Sttop.vn=0)/*(1)式*/ Sttop.vf=1; Sttop.tag=0; else/*(2)式*/ top+; Sttop.vn=Sttop-1.vn-1; Sttop.tag=1; ,3 递归非递归的转换方法1-表述2,else if (Sttop.tag=0) /*已计算

14、出vf值*/ Sttop-1.vf=Sttop-1.vn*Sttop.vf; /*(2)式*/ Sttop-1.tag=0; top-; /*栈中只有一个已求出vf的元素时退出循环*/ if (top=0 ,3 递归非递归的转换方法1-表述2,练习 以N=5为例，完整的在纸上模拟整个算法的运算过程，以此加深对表述2的理解。 以表述2方法，求斐波那契数的栈模拟递归算法。 其中，斐波那契数（Fobanacci）定义如下： f(1)=1 f(2)=1 f(n)=f(n-1)+f(n-2),其中n=2,3 递归非递归的转换方法2,利用栈保存参数：该方法通常以栈为保存运行中间数据的媒介。 例：二叉树的中

15、序遍历。 DFS( T ) DFS(T-lchild); Visit( T ); DFS(T-rchild);,3 递归非递归的转换方法2,Status InOrder(BiTree root, Status(* Visit)(ElemType e) /*中序遍历二叉树, root指向二叉树(或某一子树) */ if (root! =NULL) if( InOrder(root -LChild, visit) /*遍历左子树*/ if(Visit(root -data) /*访问根结点*/ if(InOrder(root -RChild , visit) /*遍历右子树*/ return OK

16、; return Error; else return OK; ,3 递归非递归的转换方法2,利用栈来模拟整个遍历过程，再根据遍历写出算法。,3 递归非递归的转换方法2,void InOrder（BiTree root） /* 中序遍历二叉树的非递归算法 */ InitStack (S); p=root; while(p! =NULL | !IsEmpty(S) if (p! =NULL) /* 根指针进栈， 遍历左子树 */ Push(S, p); p=p-LChild; else /*根指针退栈， 访问根结点， 遍历右子树*/ Pop(S, p); Visit(p-data); p=p-R

17、Child; /end of while ,3 递归非递归的转换方法3,利用迭代消除递归：通过分析，跳过分解过程，直接用循环结构的算法实现求值过程。 斐波那契数（Fobanacci）定义如下： f(1)=1 f(2)=1 f(n)=f(n-1)+f(n-2),其中n=2 从中找出循环求值。,3 递归非递归的转换方法3,求解Fibonacci数列的算法如下： int Fib(int n) int i,f1,f2,f3; if (n=1 | n=2) return(n); f1=1;f2=2; for (i=3;i=n;i+) f3=f1+f2; f1=f2;f2=f3; return(f3); ,3 递归非递归的转换方法3,利用迭代求解的难点：要很好地理解整个算法的思想，然后重新设计一个合理的迭代过程。,0-1背包问题,0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。 价值 体积,3 递归非递归的转换方法3,建立模型分析：定义m(i，j)是背包容量为j，可选择物品为i，i