递归与非递归程序的转换

《递归与非递归程序的转换》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、它反映递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：fun(0)=1n=0(1)fun(n)=n*fun(n-1)n>0(2)其中：第一个式子给出了递归的终止条件,我们称之为递归出口；第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系，我们称之为递归体。1递归算法的设计一般地,一个递归模型是由递归出口和递归体两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。递归出口的一般格式如下：f(s1)=m1这里的s1与m1均为常量,有些递归问题可能有几个递归出口。1递归算法的设计递归体的

4、一般格式如下：f(sn+1)=g(f(si),f(si+1),…,f(sn),cj,cj+1,…,cm)其中,n,i,j,m均为正整数。sn+1是一个递归“大问题”,si,si+1,…,sn为递归“小问题”,cj,cj+1,…,cm是可以用非递归方法直接解决的问题g是一个非递归函数,可以直接求值。1递归算法的设计递归思路实际上，递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决(此时分解到递归出口

5、)。但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似。并且有一个分解的终点。从而使问题可解。1递归算法的设计逐步分解和组合求值的过程1递归算法的设计斐波那契数：一个大问题分解为多个小问题的过程1递归算法的设计算法设计：先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法，于是可以再将它们划分成若干个子问题，分别求解，如此反复进行，直到不能再划分成子问题，或已经可以求解为止。这种自上而下将问题分解、求解，再自上而下引用、合

6、并，求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。1递归算法的设计递归设计的步骤如下：(1)对原问题f(s)进行分析,假设出合理的“较小问题”f(s')(与数学归纳法中假设n=k-1时等式成立相似)；(2)假设f(s')是可解的,在此基础上确定f(s)的解,即给出f(s)与f(s')之间的关系(与数学归纳法中求证n=k时等式成立的过程相似)；(3)确定一个特定情况(如f(1)或f(0))的解,由此作为递归出口(与数学归纳法中求证n=1时等式成立相似)。1递归算法的设计课堂练习：采用递归算法求实数数组

7、A[0..n-1]中的最小值。基本步骤：先定义清楚问题；写出递归模型；转换为算法。2为什么：递归非递归？引例求如下函数值Sum(1..X)=X+Sum(1..X-1)X>0Sum(1..X)=0X<=0它的程序？2为什么：递归非递归？利用递归求该函数#include"stdafx.h"#includeusingnamespacestd;int_tmain(intargc,_TCHAR*argv[]){cout<

8、urn0;returnx+add(x-1);}2为什么：递归非递归？利用非递归(迭代)求该函数#include"stdafx.h"#includeusingnamespacestd;int_tmain(intargc,_TCHAR*argv[]){cout<