下载文档原格式
函数的递归调用
函数的递归调用是一种技术，可用于构建更复杂的程序。
它是函数调用自己，或使用函数调用其他函数，以及由这些函数递归调用自身，构成了函数的递归调用。
在程序设计中，函数的递归调用可以帮助我们解决一些比较复杂的问题，可以更加高效地实现程序的执行任务。
在函数的递归调用过程中，函数对于自身调用的次数和内存消耗的多少是可控的。
函数的递归调用的基本概念是，函数在其函数体内部调用自身，而函数的递归调用重复多次，这种机制可以大大提高程序的效率，以及实现复杂程序的效果。
举个例子，假设我们要求计算指定范围内的数字之和，使用普通的加法运算无法满足需求，这时我们就可以通过函数的递归调用来实现这一操作。
通过函数的递归调用，我们可以将求和的操作解耦为两个部分：第一步，先找出指定数字的最后一个数字，将其加上已经求解过的结果；第二步，将比最后一个数字小的数字累加，将他们与第一步的结果相加即可得出最终结果。
此外，函数的递归调用还可以用于数学和算法中，比如排列组合、汉诺塔等等。
排列组合的问题可以使用递归调用的方法，每次都递归调用自身，排列出新的组合；汉诺塔的游戏也可以使用递归调用的方法，每次都将上层的圆盘移动到不同的柱子上，递归地完成游戏的解决。
函数的递归调用是一种很有用的技术，它可以使程序更加有效，
也可以帮助我们解决一些复杂的问题。
虽然函数的递归调用有一定的性能影响，但是也可以通过程序优化来解决，以得到更高性能的效果。
函数的递归调用是一种有效的程序设计方法，可以帮助我们更加高效地完成任务。
递归算法详解范文递归是一种常用的算法思想，它通常用于解决可以被划分为更小规模相同问题的情况。
在递归算法中，问题被分解成更小的子问题，逐步求解子问题，最终得到整个问题的解。
接下来，我将详细介绍递归算法的原理、特点和应用。
一、递归算法的原理递归算法的原理是基于函数调用的特性。
在递归算法中，函数可以调用其自身来解决更小规模的子问题。
每次递归调用会将问题分解为更小规模的子问题，直到达到边界条件，然后逐步返回结果，最终得到整个问题的解。
递归算法通常具有以下两个重要的特点：1.递归定义：递归算法通过将问题分解为更小规模的子问题来定义。
2.递归调用：递归算法通过调用自身来解决更小规模的子问题。
递归算法的实现通常包含两个部分：基本情况和递归情况。
1.基本情况：基本情况是递归算法的边界条件，它表示问题已经足够小，可以直接求解，无需继续递归调用。
2.递归情况：递归情况是递归算法的重点，它描述了如何将当前问题分解为更小规模的子问题，并调用自身来解决子问题。
递归算法在实现时需要注意以下几点：1.基本情况的设置要合理，以确保算法能够终止。
2.递归调用时，问题规模要比上一次递归调用减小，确保算法能够在有限步骤内得到解。
3.递归算法的效率通常比较低，因为它会重复计算一些子问题。
可以通过记忆化、动态规划等方法进行优化。
二、递归算法的特点递归算法具有以下几个特点：1.逻辑简单清晰：递归算法的实现通常比较简洁，容易理解和调试。
2.代码复用性好：递归算法可以将问题分解为更小规模的子问题，这样可以复用代码来解决不同规模的问题。
3.可读性强：递归算法通常可以直观地反映问题的结构和解题思路。
4.可扩展性好：递归算法可以方便地将问题扩展到更大规模。
然而，递归算法也存在一些局限性：1.递归算法通常会消耗较多的内存空间，因为每一次递归调用都需要保存一些中间结果。
2.递归算法的效率较低，因为它会存在重复计算的问题，可以通过优化方法进行提升。
3.递归算法可能会因为递归过深而导致栈溢出，需要注意递归调用的次数。
分治策略（求解递归式的⽅法）分解：将原问题划分成形式相同的⼦问题，规模可以不等，对半或2/3对1/3的划分。
解决：对于⼦问题的解决，很明显，采⽤的是递归求解的⽅式，如果⼦问题⾜够⼩了，就停⽌递归，直接求解。
合并：将⼦问题的解合并成原问题的解。
这⾥引出了⼀个如何求解⼦问题的问题，显然是采⽤递归调⽤栈的⽅式。
因此，递归式与分治法是紧密相连的，使⽤递归式可以很⾃然地刻画分治法的运⾏时间。
所以，如果你要问我分治与递归的关系，我会这样回答：分治依托于递归，分治是⼀种思想，⽽递归是⼀种⼿段，递归式可以刻画分治算法的时间复杂度。
解递归式:这⾥有三种⽅法：代⼊法、递归树法和主⽅法。
（下⾯这⼀部分结合有些⽹友的总结和我的总结得来）代⼊法：定义：先猜测某个界的存在，再⽤数学归纳法去证明该猜测的正确性。
缺点：只能⽤于解的形式很容易猜的情形。
总结：这种⽅法需要经验的积累，可以通过转换为先前见过的类似递归式来求解。
递归树法：起因：代换法有时很难得到⼀个正确的好的猜测值。
⽤途：画出⼀个递归树是⼀种得到好猜测的直接⽅法。
分析(重点)：在递归树中，每⼀个结点都代表递归函数调⽤集合中⼀个⼦问题的代价。
将递归树中每⼀层内的代价相加得到⼀个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。
总结：递归树最适合⽤来产⽣好的猜测，然后⽤代换法加以验证。
递归树的⽅法⾮常直观，总的代价就是把所有层次的代价相加起来得到。
但是分析这个总代价的规模却不是件很容易的事情，有时需要⽤到很多数学的知识。
主⽅法：主⽅法是最好⽤的⽅法，书本上以”菜谱“来描述这种⽅法的好⽤之处，它可以瞬间估计⼀个递推式的算法复杂度。
但是我们知道，这后⾯肯定是严格的数学证明在⽀撑着，对于我们⽤户来说，我们只⽤知道怎么⽤就⾏了。
优点：针对形如T(n) = af(n/b) + f(n)的递归式缺点：并不能解所有上述形式的递归式，有⼀些特殊情况，见下⽂分析。
分析：三种情况，如下图，着重看圈线的部分:直觉：看 f(n) 和 n log b a 的关系，谁⼤取谁，相等则两个相乘，但要注意看是否相差因⼦ nε。
函数的递归调用与分治策略 ——以C++为例
Original version by Wecan Dec.27th, 2005
递归方法是算法和程序设计中的一种重要技术。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题。递归方法具有易于描述和理解、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。递归方法中所使用的“分而治之”的策略也称分治策略。
递归方法的构造 构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。下面由一个求n的阶乘的程序为例，总结出构造递归方法的一般步骤。
[例1]从键盘输入正整数N（0<=N<=20），输出N!。 [分析]N!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。 [步骤1]描述递归关系 递归关系是这样的一种关系。设{U1,U2,U3,…,Un…}是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。 注意到，当N>=1时，N!=N*(N-1)!（N=1时，0!=1），这就是一种递归关系。对于特定的K!，它只与K与(K-1)!有关。 [步骤2]确定递归边界 在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。 确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序： #include int f(int x){ return(f(x-1)); } main(){ cout<} 它没有规定递归边界，运行时将无限循环，会导致错误。 [步骤3]写出递归函数并译为代码 将步骤1和步骤2中的递归关系与边界统一起来用数学语言来表示，即 N*(N-1)! 当N>=1时 n!= 1 当N=0时 再将这种关系翻译为代码，即一个函数： long f(int n){ if (n==0) return(1); else return(n*f(n-1)); } [步骤4]完善程序 主要的递归函数已经完成，将程序依题意补充完整即可。 //ex1.cpp #include long f(int n){ if (n==0) return(1); else return(n*f(n-1)); } main(){ int n; cin>>n; cout<} 综上，得出构造一个递归方法基本步骤，即描述递归关系、确定递归边界、写出递归函数并译为代码，最后将程序完善。以下继续引用一些例子来讨论递归方法的应用。
经典递归问题 以下讨论两个十分经典的递归问题。它们的算法构造同样遵循刚刚得出的四个步骤。了解这两个问题可加深对递归方法的理解。
[例2]Fibonacci数列（兔子繁殖）问题：已知无穷数列A，满足：
A(1)=A(2)=1，A(N)=A(N-1)+A(N-2)（N>=3）。从键盘输入N，输出A(N)。 [分析]递归关系十分明显，由A(N)的表达式给出。需要注意的是本例中对于N>=3，A(N)的值与A(N-1)和A(N-2)都有关。 [代码] //ex2.cpp #include long fibonacci(int x) { if ( (x==1) || (x==2) ) return(1); else return(fibonacci(x-1)+fibonacci(x-2)); } main(){ int n; cin>>n; cout>>endl>>fibonacci(n); }
[例3]Hanoi塔问题。 [问题描述]在霍比特人的圣庙里，有一块黄铜板，上面插着3根宝石针（分别为A号，B号和C号）。在A号针上从下到上套着从大到小的n个圆形金片。现要将A针上的金片全部移到C针上，且仍按照原来的顺序叠置。移动的规则如下：这些金片只能在3根针间移动，一次只能一片，且任何时候都不允许将较大的金片压在较小的上面。从键盘输入n，要求给出移动的次数和方案。 [分析]由金片的个数建立递归关系。当n=1时，只要将唯一的金片从A移到C即可。当n>1时，只要把较小的(n-1)片按移动规则从A移到B，再将剩下的最大的从A移到C（即中间“借助”B把金片从A移到C），再将B上的(n-1)个金片按照规则从B移到C（中间“借助”A）。 本题的特点在于不容易用数学语言写出具体的递归函数，但递归关系明显，仍可用递归方法求解。 [代码] //ex3.cpp #include hanoi(int n,char t1,char t2,char t3){ if (n==1) cout<<"1 "< else { hanoi(n-1,t1,t3,t2); cout< hanoi(n-1,t2,t1,t3); } } main(){ int n; cout<<"Please enter the number of Hanoi:"; cin>>n; cout<<"Answer:"< hanoi(n,'A','B','C'); } 函数递归调用的应用与分治策略 许多算法都采用了分治策略求解，而可以说分治与递归是一对孪生兄弟，它们经常同时被应用于算法的设计中。下面讨论著名的Catalan数问题，人们在对它的研究中充分应用了分治策略。
[例4]Catalan数问题。 [问题描述]一个凸多边形，通过不相交于n边形内部的对角线，剖分为若干个三角形。求不同的剖分方案总数H(n)。H(n)即为Catalan数。例如，n=5时H(5)=5。 [分析]Catalan数问题有着明显的递归子问题特征。在计算Catalan数时虽然可以推导出只关于n的一般公式，但在推导过程中却要用到递归公式。下面讨论三种不同的解法，其中第三种解法没有使用递归，它是由前两种解法推导而出的。 [解法1]对于多边形V1V2…Vn，对角线V1Vi（i=3,4,…,n-1）将其分为两部分，一部分是i边形，另一部分是n-i+1边形。因此，以对角线V1Vi为一个剖分方案的剖分方案数为H(i)*H(n-i+1)。还有一种的特殊情形，是对角线V2Vn将其分为一个三角形V1V2Vn和一个n-2+1边形。为了让它同样符合粗体字给出的公式，规定H(2)=1。于是得到公式： H(n)=∑H(i)*H(n-i+1) （i=2,3,…,n-1） ----公式(1) H(2)=1 有了这个递归关系式，就可以用递推法或递归法解出H(n)。 [解法2]从V1向除了V2和Vn外的n-3个顶点可作n-3条对角线。每一条对角线V1Vi把多边形剖分成两部分，剖分方案数为H(i)*H(n-i+2)，由于Vi可以是V3V4…Vn-1中的任一点，且V1可换成V2，V3，…，Vn中任一点也有同样的结果。考虑到同一条对角线在2个顶点被重复计算了一次，于是对每个由顶点和对角线确定的剖分方案都乘以1/2，故有 H(n)=n∑(1/2)H(i)*H(n-i+2) （i=3,4,…,n-1） 把(1/2)提到∑外面， H(n)=n/(2*(n-3))∑H(i)*H(n-i+2) （i=3,4,…,n-1） ----公式(2) 规定H(2)=H(3)=1，这是合理的。 由公式(2)和H(2)=1，同样可以用递推法或递归法解出H(n)。 [解法3] 把公式(1)中的自变量改为n+1，再将刚刚得出的公式(2)代入公式(1)，得到 H(n+1)=∑H(i)*H(n-i+2) （i=2,3,…,n） 由公式(1) H(n+1)=2*H(n)+∑H(i)*H(n-i+2) （i=3,4,…,n-1） 由H(2)=1 H(n+1)=(4n-6)/n*H(n) 由公式(2) H(n)=(4n-10)/(n-1)*H(n-1) ----公式(3) 这是一个较之前两种解法更为简单的递归公式，还可以继续简化为 H(n)=1/(n-1)*C(n-2,2n-4) ----公式(4) 这就不需要再使用递归算法了。然而在程序设计上，公式(4)反而显得更加复杂，因为要计算阶乘。因此最后给出由公式(3)作为理论依据范例程序代码。代码相当简单，这都归功于刚才的推导。如果用前两种解法中的递归关系，程序会变得复杂且容易写错。因此，有时对具体问题将递归关系公式进行必要的化简也是至关重要的。 [代码] //ex4.cpp #include #define MAXN 100 long f(int x){ if (x==3) return(1); else return((4*x-10)*f(x-1)/(x-1)); } main(){ int n; cout<<"\nPlease input N for a Catalan number:"; cin>>n; if ( (n<=MAXN) && (n>=3) ) cout<<"The answer is:"<} 本例编程时还有一个细节问题需要注意。注意函数f中的斜体部分，按照公式(4)计算时一定要先进行乘法再进行除法运算，因为(4*x-10)并不总能整除(x-1)，如果先进行除法则除出的小数部分将自动被舍去，从而导致得到不正确的解。 数学上许多有重要意义的计数问题都可以归结为对Catalan数的研究。可以看到，本例中的递归关系经简化还是相当简单的。下面讨论一个递归关系略为复杂的例子。
[例5]快速排序问题。 快速排序是程序设计中经常涉及的一种排序算法。它的最好时间复杂度为O(nlog2n)，最差为O(n2)，是一种不稳定的排序方法（大小相同的数在排序后可能交换位置）。 [算法描述]快速排序的一种基本思想是：要将n个数按由小到大排列，在待排序的n个数中选取任一个数（在本例中取第一个），称为基准数，在每一次快速排序过程中设置两个指示器i和j，对基准数左边和右边的数同时从最左（i）和最右（j）开始进行扫描（i逐1递增，j逐1递减），直到找到从左边开始的某个i大于或等于基准数，从右边开始的某个j小于或等于基准数。一旦发现这样的i和j（暂且称之为一个“逆序对”），则把第i个数和第j个数交换位置，这样它们就不再是逆序对了，紧接着再将i递增1，j递减1。如此反复，在交换过有
限个逆序对后，i和j将越来越靠近，最后“相遇”，即i和j指向同一个数，暂且称之为相遇数（极端情况下，如果一开始就不存在逆序对，i和j将直接“相遇”）。相遇后就保证数列中没有逆序对了（除了在上述的极端情况下基准数和自身也算构成一个逆序对，注意粗体字给出的逆序对的定义）。继续扫描，非极端情况下，由于数列中已经没有逆序对，i递增1（如果相遇数小于基准数）或者j递减1（如果相遇数大于基准数）后即算完成了一趟快速排序，这时第1到第j个数中的每个都保证小于或等于基准数，第i到第n个数中的每个保证大于或等于基准数。此时，递归调用函数，对第1到第j个数和第i到第n个数分别再进
