递归算法

数据结构论文——递归算法的讨论所谓递归算法是把问题转化为规模缩小了的同类问题的子问题。

然后递归调用函数（或过程）来表示问题的解。

一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)。

递归过程一般通过函数或子过程来实现。

递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。

递归算法是一种直接或者间接地调用自身算法的过程。

在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。

递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。

递归次数过多容易造成栈溢出等。

所以一般不提倡用递归算法设计程序。

下面就让我们结合例子详细讨论一下递归算法。

一、递归算法的原理递归算法简单的说就是在函数中调用函数自身，不断调用，直到满足函数得出计算结果(某个条件)。

因为其需要不断循环的调用自身，所以称为递归调用。

递归的原理,其实就是一个栈(stack), 比如求5的阶乘,要知道5的阶乘,就要知道4的阶乘,4又要是到3的,以此类推,所以递归式就先把5的阶乘表示入栈, 在把4的入栈,直到最后一个,之后呢在从1开始出栈, 看起来很麻烦,确实很麻烦,他的好处就是写起代码来,十分的快,而且代码简洁,其他就没什么好处了,运行效率出奇的慢。

还有一个十分形象的例子：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事……如此循环往复到最终的要求。

递归分为2种，直接递归和间接递归。

直接递归，比如方法A内部调用方法A自身。

间接递归，比如方法A内部调用方法B，方法B内部调用方法C，方法C 内部调用方法A。

递归算法知识点总结一、基本概念递归算法的基本概念是基于递归函数的思想。

递归函数是一个调用自身的函数。

递归算法通常可以分为两种类型：简单递归和复杂递归。

简单递归是指在递归函数中直接调用自身，而复杂递归则是指在递归函数中可能会有多个递归调用。

递归算法通常用于解决可以分解为若干子问题的问题，这种方法通常可以更加简洁地解决问题，但同时也可能会带来一些计算复杂度的问题。

递归算法的设计通常包括以下几个步骤：1. 确定基本情况：在设计递归函数时，通常需要确定一个或多个基本情况。

基本情况通常是指在递归函数中不需要再次调用自身的情况。

2. 确定递归情况：在设计递归函数时，需要确定一个或多个递归情况。

递归情况通常是指在递归函数中需要调用自身的情况。

3. 确定递归方式：当确定了递归函数的基本情况和递归情况之后，就需要确定递归函数的调用方式。

通常有两种方式：直接递归和间接递归。

4. 编写递归函数：根据确定的基本情况、递归情况和递归方式，编写递归函数。

5. 测试递归函数：编写递归函数后，需要对递归函数进行测试，确保递归函数能够正确地解决问题。

二、递归算法的原理递归算法的原理是基于递归函数的调用。

当一个递归函数被调用时，它会将自身的执行环境保存到栈中，并且在栈中分配一些空间。

在递归函数中，如果有一些局部变量，这些变量会在栈中分配空间。

随着递归函数的深入调用，栈中的空间也会不断增加。

在递归函数的执行过程中，通常需要考虑递归栈的压栈和出栈操作。

在递归函数被调用时，会执行一些初始化操作，并将递归参数保存到栈中。

在递归函数中，如果遇到递归情况，会再次调用自身，并且将自身的执行环境保存到栈中。

在递归函数的执行过程中，如果遇到基本情况，就会结束当前递归调用，并且从栈中释放空间。

递归算法的原理是基于递归函数的深度调用的。

当递归函数被调用时，会执行一些初始化过程，并将递归参数保存到栈中。

当递归函数执行完毕后，会从栈中释放空间。

在递归函数的执行过程中，栈中的空间会不断增加和释放。

递归算法详解完整版递归算法是一种重要的算法思想，在问题解决中起到了很大的作用。

它通过将一个大问题划分为相同或类似的小问题，并将小问题的解合并起来从而得到大问题的解。

下面我们将详细介绍递归算法的定义、基本原理以及其应用。

首先，我们来定义递归算法。

递归算法是一种通过调用自身解决问题的算法。

它通常包括两个部分：基础案例和递归步骤。

基础案例是指问题可以被直接解决的边界情况，而递归步骤是指将大问题划分为较小问题并通过递归调用自身解决。

递归算法的基本原理是"自顶向下"的思维方式。

即从大问题出发，不断将问题划分为较小的子问题，并解决子问题，直到达到基础案例。

然后将子问题的解合并起来，得到原始问题的解。

递归算法的最大特点是简洁而优雅。

通过将复杂问题分解为简单问题的解决方式，可以大大减少代码的复杂程度，提高程序的效率和可读性。

但是递归算法也有一些缺点，包括递归深度的限制和复杂度的不确定性。

过深的递归调用可能导致栈溢出，而不合理的递归步骤可能导致复杂度过高。

递归算法有许多应用场景，我们来介绍其中一些典型的应用。

1.阶乘问题：计算一个数的阶乘。

递归算法可以通过将问题划分为更小的子问题来解决。

例如，n的阶乘可以定义为n乘以(n-1)的阶乘。

当n 等于1时，我们可以直接返回1作为基础案例。

代码如下：```int factorial(int n)if (n == 1)return 1;}return n * factorial(n - 1);```2.斐波那契数列问题：求斐波那契数列中第n个数的值。

斐波那契数列的定义是前两个数为1，然后从第三个数开始，每个数都是前两个数的和。

递归算法可以通过将问题划分为两个子问题来解决。

当n等于1或2时，直接返回1作为基础案例。

代码如下：```int fibonacci(int n)if (n == 1 ， n == 2)return 1;}return fibonacci(n - 1) + fibonacci(n - 2);```3.二叉树问题：对于给定的二叉树，递归算法可以通过递归调用左子树和右子树的解来解决。

6种基本算法递归递归是一种重要的算法思想，它在计算机科学中得到广泛应用。

本文将介绍六种基本的递归算法，并对其原理和应用进行讲解。

一、递归的基本概念递归是指一个函数在其定义中调用自身的过程。

递归算法通过将一个大问题划分为一个或多个相同或相似的子问题，然后通过解决子问题来解决原始问题。

递归算法具有简洁、优雅以及可读性强的特点，但同时也需要注意递归的停止条件，以避免无限递归的发生。

二、阶乘算法阶乘算法是递归算法中最经典的例子之一。

它的定义如下：```n! = n * (n-1) * (n-2) * ... * 1```其中，n为一个非负整数。

阶乘算法可以通过递归的方式实现，即：```fact(n) = n * fact(n-1)```其中，停止条件为`n=0`时，返回1。

三、斐波那契数列算法斐波那契数列是一个无限序列，其定义如下：```F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2) (n>1)```斐波那契数列算法可以通过递归的方式实现，即：```fib(n) = fib(n-1) + fib(n-2)```其中，停止条件为`n=0`或`n=1`时，返回相应的值。

四、二分查找算法二分查找算法是一种高效的查找算法，它的基本原理是将已排序的数组分成两部分，然后判断目标值在哪一部分，并继续在该部分中进行查找，直到找到目标值或者查找范围为空。

二分查找算法可以通过递归的方式实现，即：```binarySearch(arr, target, start, end) = binarySearch(arr, target, start, mid-1) (target < arr[mid])= binarySearch(arr, target, mid+1, end) (target > arr[mid])= mid (target = arr[mid])```其中，`arr`为已排序的数组，`target`为目标值，`start`和`end`为查找范围的起始和结束位置。

递归算法得优缺点：3优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法得正确性，因此它为设计算法、调试程序带来很大方便。

3缺点：递归算法得运行效率较低，无论就是耗费得计算时间还就是占用得存储空间都比非递归算法要多。

边界条件与递归方程就是递归函数得二个要素应用分治法得两个前提就是问题得可分性与解得可归并性以比较为基础得排序算法得最坏倩况时间复杂性下界为0(n I o g2n)。

回溯法以深度优先得方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先得方式搜索解空间树T。

舍伍德算法设计得基本思想：设A就是一个确定性算法，当它得输入实例为x时所需得计算时间记为tA(x)。

设Xn就是算法A得输入规模为n得实例得全体，则当问题得输入规模为n时，算法A所需得平均时间为这显然不能排除存在x€Xn使得得可能性。

希望获得一个随机化算法B，使得对问题得输入规模为n得每一个实例均有拉斯维加斯(Las Vegas )算法得基本思想：设p(x)就是对输入x调用拉斯维加斯算法获得问题得一个解得概率。

一个正确得拉斯维加斯算法应该对所有输入x均有p(x)>0。

设t(x)就是算法obst in ate找到具体实例x得一个解所需得平均时间，s(x)与e(x)分别就是算法对于具体实例x求解成功或求解失败所需得平均时间，则有：解此方程可得：蒙特卡罗(Monte Carlo)算法得基本思想：设p就是一个实数，且1/2<p<1。

如果一个蒙特卡罗算法对于问题得任一实例得到正确解得概率不小于p,则称该蒙特卡罗算法就是p正确得，且称p1/2就是该算法得优势。

如果对于同一实例，蒙特卡罗算法不会给出2个不同得正确解答，则称该蒙特卡罗算法就是一致得。

线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。

单纯形算法得特点就是：(1) 只对约束条件得若干组合进行测试，测试得每一步都使目标函数得值增加；(2) 一般经过不大于m或n次迭代就可求得最优解。

递归算法的优缺点递归算法是一种使用自身定义的函数来解决问题的方法。

递归算法的优点包括简洁、直观，能够将问题转化为较小的相同问题进行解决。

然而，递归算法也存在一些缺点，包括效率低下、可能引发栈溢出等问题。

首先，递归算法的优点是简洁、直观。

递归算法通常能够将原始问题转化为较小的子问题，然后通过调用自身函数来解决这些子问题。

这种简洁的方式使得算法的实现更加直观和易于理解。

相比于迭代算法，递归算法往往具有更少的代码量，使得代码更加简洁优雅。

其次，递归算法能够提供一种自顶向下的问题解决方式。

递归算法可以将复杂的问题分解为更小的子问题，然后逐步解决这些子问题，在子问题解决完成后再进行逐步合并，最终得到原始问题的解。

这种自顶向下的思维方式使得问题的解决过程更加直观、易于理解。

此外，递归算法还具有形式上的优点。

递归算法在问题的定义上使用了自身函数的调用，使得代码的结构更加紧凑和简洁。

递归算法的代码常常能够简洁地反映问题的本质，使得代码更加易于维护和扩展。

然而，递归算法也存在一些缺点。

首先，递归算法的效率往往较低。

递归算法在解决问题时需要频繁地调用自身函数，而函数调用涉及到压栈和出栈的过程，会带来额外的开销。

在一些情况下，递归算法的效率可能远远低于迭代算法。

其次，递归算法容易引发栈溢出的问题。

每次递归调用函数时，系统都需要为该函数分配一定的栈空间。

如果递归调用的层数过多，就会导致栈空间不足，从而引发栈溢出的问题。

为了避免栈溢出，需要限制递归调用的深度，或者使用尾递归优化等技术手段。

此外，递归算法的实现往往需要额外的空间开销。

每次递归调用函数时，都需要保存函数的局部变量、参数值等信息，以便后续的出栈和恢复操作。

这些额外的空间开销会占用较多的内存，特别是在递归调用的次数较多时。

最后，递归算法可能出现递归陷阱的问题。

递归陷阱是指当递归算法的终止条件不满足时，递归调用会一直持续下去，导致程序无法正常终止。

为了避免递归陷阱，必须正确地设计和实现递归算法的终止条件，以确保程序能够正常结束。

4563697
4564531 4565926
正中间 的元素
4566088
4572874
17
4120243
4276013
4328968 4397700
4462718
请问： 4565926是否在 此列表当中？ 4565925？
4466240 4475579
4478964
4480332 4494763
4499043
相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行
简单调用就能来完成特定功能。

例如我们把上面的讲故事的过程包装成一个函数，就会得到：
void Story() { puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故 事，它讲的故事是："); getchar();//按任意键听下一个故事的内容 Story(); //老和尚讲的故事，实际上就是上面那个故事 }
4563697
4564531 4565926
4566088
4572874
16
4120243
4276013
4328968 4397700
4462718
请问： 4565926是否在 此列表当中？
4466240 4475579
4478964
4480332 4494763
4499043
4508710 4549243

(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时等式 成立相似)。

数据结构常考的5个算法1. 递归算法递归是一种将问题分解为相同或相似的子问题解决的方法。

在递归算法中，一个函数可以调用自己来解决更小规模的问题，直到遇到基本情况，然后递归返回并解决整个问题。

递归算法通常用于解决需要重复执行相同操作的问题，例如计算斐波那契数列、计算阶乘、树和图的遍历等。

递归算法的主要特点是简洁、易理解，但在大规模问题上可能效率较低。

以下是一个使用递归算法计算斐波那契数列的示例代码：def fibonacci(n):if n <= 1:return nelse:return fibonacci(n-1) + fibonacci(n-2)2. 排序算法排序算法用于将一组数据按照一定顺序进行排列。

常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。

•冒泡排序逐渐交换相邻的元素，将较大的元素逐渐“冒泡”到最后的位置。

•选择排序每次选择最小（或最大）的元素，并将其放置在已排序部分的末尾。

•插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

•快速排序通过选择一个基准元素，将数组分割为左右两部分，对左右两部分分别递归地进行快速排序。

•归并排序将数组分成两个子数组，分别对两个子数组进行排序，然后将两个有序子数组合并为一个有序数组。

以下是一个使用快速排序算法对数组进行排序的示例代码：def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr)//2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)3. 查找算法查找算法用于在数据集合中查找特定元素的位置或存在性。

递归算法及经典递归例⼦代码实现递归（recursion）：程序调⽤⾃⾝的编程技巧。

递归满⾜2个条件：1）有反复执⾏的过程（调⽤⾃⾝）2）有跳出反复执⾏过程的条件（递归出⼝）递归例⼦：（1）阶乘n! = n * (n-1) * (n-2) * ...* 1(n>0)//阶乘int recursive(int i){int sum = 0;if (0 == i)return (1);elsesum = i * recursive(i-1);return sum;}（2）河内塔问题//河内塔void hanoi(int n,int p1,int p2,int p3){if(1==n)cout<<"盘⼦从"<<p1<<"移到"<<p3<<endl;else{hanoi(n-1,p1,p3,p2);cout<<"盘⼦从"<<p1<<"移到"<<p3<<endl;hanoi(n-1,p2,p1,p3);}}（3）全排列从n个不同元素中任取m（m≤n）个元素，按照⼀定的顺序排列起来，叫做从n个不同元素中取出m个元素的⼀个排列。

当m=n时所有的排列情况叫全排列。

如1,2,3三个元素的全排列为：1,2,31,3,22,1,32,3,13,1,23,2,1//全排列inline void Swap(int &a,int &b){int temp=a;a=b;b=temp;}void Perm(int list[],int k,int m){if (k == m-1){for(int i=0;i<m;i++){printf("%d",list[i]);}printf("n");}else{for(int i=k;i<m;i++){Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}}（4）斐波那契数列斐波纳契数列，⼜称黄⾦分割数列，指的是这样⼀个数列：1、1、2、3、5、8、13、21、……这个数列从第三项开始，每⼀项都等于前两项之和。

前言说白了递归就象我们讲的那个故事：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：……也就是直接或间接地调用了其自身。

就象上面的故事那样，故事中包含了故事本身。

因为对自身进行调用，所以需对程序段进行包装，也就出现了函数。

函数的利用是对数学上函数定义的推广，函数的正确运用有利于简化程序，也能使某些问题得到迅速实现。

对于代码中功能性较强的、重复执行的或经常要用到的部分，将其功能加以集成，通过一个名称和相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行简单调用就能来完成特定功能。

例如我们把上面的讲故事的过程包装成一个函数，就会得到：void Story(){puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：");getchar();//按任意键听下一个故事的内容Story(); //老和尚讲的故事，实际上就是上面那个故事}函数的功能是输出这个故事的内容，等用户按任意键后，重复的输出这段内容。

我们发现由于每个故事都是相同的，所以出现导致死循环的迂回逻辑，故事将不停的讲下去。

出现死循环的程序是一个不健全的程序，我们希望程序在满足某种条件以后能够停下来，正如我们听了几遍相同的故事后会大叫：“够了！”。

于是我们可以得到下面的程序：#include<stdio.h>const int MAX = 3;void Story(int n);//讲故事int main(void){Story(0);getchar();return 0;}void Story(int n){if (n < MAX){puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚对小和尚说了一个故事：");getchar();Story(n+1);}else{printf("都讲%d遍了！你烦不烦哪？\n", n);return ;}}上面的Story函数设计了一个参数n，用来表示函数被重复的次数，当重复次数达到人们忍受的极限（MAX次）时，便停下来。

/*
递归算法：
1.自身函数中调用自己的函数。执导
2.递归结束的条件应放在递归函数之前。否则就会形成无穷循环调用。
3.每一次递归定义的变量都会保留在本次调用过程中，等到返回时，就可以得到变量的值。每一次调用过程中所定义的变量的值是不同的。
4.每一次调用时都会有类似中断的保护现场，等本次调用结束后返回该调用电继续执行语句。
printf("输入需要转换进制的数值：\n");
scanf("%d",&old); //输入需要转换的数字
printf("输入需要转换为的进制：\n");
scanf("%d",&base);
convto(s,old,base); //调用转换函数，s为转换后的数值
printf("%s\n",s);
printf("调用过后！！！！\n");
len = strlen(s);
s[len] = bit[n%b];
s[len+1] = '\0';
}
int main()
{
char s[80]; //定义了一个字符数组
int base,old; //old需要转换为其他进制的数，base为进制数可以为2、8、10、16
{
char bit[] = {"0123456789ABCDEF"}; //不同进制数数值
int len;
if(n == 0)
{
strcpy(s," ");
printf("这
printf("开始调用\n");

if( knap( m-m[n],n-1 )) return true;
return knap(m,n-1); }
3.递归算法设计
递归算法
算法设计和分析
递归算法
Hanoi塔问题
汉诺塔（Tower of Hanoi）游戏据说来源于布拉玛神庙。游戏的 装置如图所示（图上以3个金片例），底座上有三根金的针，第 一根针上放着从大到小64个金片。游戏的目标是把所有金片从 第一根针移到第三根针上，第二根针作为中间过渡。每次只能
建立标号：分别在过程的第一条可执行语句处、每个递归调
用处建立标号，依次为：L0,L1,L2,……，做为入口地址和返 回地址
消去递归调用：局部变量、形参、返回地址入栈,形式参数赋 值，goto语句到L0
修改函数的返回部分：
• 用户栈为空，返回 • 返回值保存到全局变量中，同时将引用参数赋给栈顶的相应变量
{
CStack<int> stack;
int retvalue,retaddr;
int res ;
L0:
if( a < b )
{
res = GCD(b,a);
L1:
;
}
else if( b == 0 )
{
res = a;
}
else
{
res = GCD(b,a%b);
L2:
;
}
return res; }
}
修改标号L1处的递归调用
算法设计和分析
递归算法
else {
//res = GCD(b,a%b); //保护现场
stack.Push(a); stack.Push(b); stack.Push(res); stack.Push(2); //返回地址 stack.Push(b); stack.Push(a%b); //设置函数的调用参数 goto L0; L2: res = retvalue; //返回值放在全局变量里 }

b)
cn k
n1 n1
O (nlog b a ) T (n) O(nk log b n) O(nk )
a bk a bk a bk
但是并非所有的递推式都可以用公式法求解。 例T(n)=2T(n/2)+nlogn 由于a=2, b=2, f(n)=nlogn和nlogba=n。看起来似乎属于 主定理情况（3），但事实上f(n)只是渐近大于n，但并不 是多项式大于n。f(n)与的nlogba比值是log n，对于任何 正数，log n渐近小于n，所以，此例不能运用定理。
1 替换方法
替换方法要求首先猜测递推式的解，然后用归纳法证明。
例2.2 T(n) 2T(n / 2) n
需要注意在上述证明过程中，没有考虑初始条件，而初始条 件是归纳法成立的基础。上例归纳证明的初始条件是是 T(1)≤c，只要选择足够大的c≥1即成立。
2.迭代方法
迭代方法的思想是扩展递推式，将递推式先转换成 一个和式，然后计算该和式，得到渐近复杂度。 例2.4 使用迭代方法分析 T (n) 2T (n / 2) n2
本章要点
• 递归算法特性
• 递推关系 • 递归算法的应用
章节内容
2.1 递归算法 2.1.1 递归算法特性 2.1.2 递归算法的执行过程 2.1.3 递推关系
2.2 递归法应用举例
2.3 典型问题的C++程序
2.4 小结
2.1 递归法
2.1.1 递归算法的特性
若一个算法直接的或间接的调用自己本身，则称这个算 法是递归算法。递归本质上也是一种循环的算法结构，它把较 复杂的计算逐次归结为较简单的情形的计算，直到归结到最简 单情形的计算，并最终得到计算结果为止。

递归算法特点
递归算法是一种程序设计思想，就是把问题划分为几个规模较小的问题处理，用同一的处理方法分别解决这个子问题，最终把小问题的答案组装起来，就得到原问题的答案，从而达到节约计算量的目的。

递归算法具有如下特点：
（1）实现简单：递归算法不一定需要实现复杂的循环，只要确定调用递归函数的调用条件就可以实现简单的递归程序。

（2）易于理解：递归算法相对于循环算法来说，更容易理解，因为算法的每一步大部分只做相同的事情，而且反复调用自身，对理解性质的程序有着极大的帮助。

（3）算法本身的特性决定的：递归算法能够处理接近无限大的计算任务，因为中间调用的关键状态可以独立处理，是由算法本身的特性决定的。

（4）避免使用复杂的循环结构：递归算法能够减少对复杂的数据结构和复杂的循环结构的使用，从而减少程序维护成本和减轻程序员负担。

（5）重复子问题：在递归算法中，同样的子问题会被多次计算，为了解决这一问题可以使用缓存策略，即记录某些子问题的计算结果，当子问题再次出现时载入缓存中的值而无需重复计算，从而节省计算量。

总之，递归算法是一种非常有用的解决方案，能够减少编程复杂度，降低程序维护成本，易于理解，容易调试，效率又较高，有相当的通用性，可以解决一些复杂的计算问题。

【例3】Hanoi汉诺塔问题
有N个圆盘，依半径大小（半径都不同），自下而上套在A柱上，每次只允 许移动最上面一个盘子到另外的柱子上去（除A柱外，还有B柱和C柱，开始时这 两个柱子上无盘子），但绝不允许发生柱子上出现大盘子在上，小盘子在下的情 况，现要求设计将A柱子上N个盘子搬移到C柱去的方法。 【算法分析】 本题是典型的递归程序设计题。 (1)当N=1 时，只有一个盘子，只需要移动一次:A—>C; (2)当N=2时，则需要移动三次： A------ 1 ------> B, A ------ 2 ------> C, B ------ 1------> C. (3)如果N=3，则具体移动步骤为：
【参考程序】 #include<iostream> #include<cstdlib> using namespace std; int a[11]; void search(int,int,int); int main() //主程序 { int k,x,L=1,R=10; cout<<"输入10个从大到小顺序的数："<<endl; for (k=1;k<=10;k++) cin>>a[k]; cin>>x; search(x,L,R); system("pause"); } void search(int x,int top,int bot) //二分查找递归过程 { int mid; if (top<=bot) { mid=(top+bot)/2; //求中间数的位置
假设把第3步，第4步，第7步抽出来就相当于N=2的情况（把上面2片 捆在一起，视为一片）：

递归算法的应用
递归算法是指在计算机科学中，一种使用自身的方法来解决一个问题的算法。

它的基本思想是将一个复杂的问题分解成一些规模较小的相同问题，将它们一一解决，然后将解决的结果合并起来，就得到原来问题的答案。

它与迭代(iteration)大体相同，不同的是迭代使用循环，而递归使用函数调用。

递归算法常用于排序和搜索算法。

例如，快速排序和归并排序就是采用递归的思想来实现的。

在游戏开发和计算机图形学等领域，也常采用递归算法。

比如大家熟悉的迷宫寻路算法就有递归实现。

此外，递归还可以用于处理树结构，如表达式树(Expression Tree)，以及图形处理中的树结构，如HTML、XML文件等。

总之，递归算法在计算机科学里被广泛使用，它使编程者可以使用少量的代码把复杂性以容易理解的形式表达出来。

它不仅可以用来解决各种规模的问题，而且在算法复杂度上也具有一定的优势。

【算法分析】递归算法的⼏个经典例⼦例⼀：整数划分问题 将正整数n表⽰成⼀系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。

正整数n的这种表⽰称为正整数n的划分。

求正整数n的不同划分个数。

例如：正整数6有如下11种不同的划分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加⼀个⾃变量：将最⼤加数n1不⼤于m的划分个数记作q(n,m)。

下⾯对可能出现的四种情况进⾏分析：① m=1： 当m等于1时，对n的划分只可能1+1+1+……+1这⼀种情况。

②m>n时： 当m⼤于n时，由于划分中不可能出现负数，所以{n1, n2, n2,… , nk}（n = n1+n2+n3+……+nk）只可能出现⼩于等于n的整数。

故有q(n, m)=q(n, n)⑤m=n时： 当m等于n时，包含n⾃⾝的划分和没有n的划分两个部分。

⽽包含n⾃⾝的划分只有⼀种情况，故有有q(n, n)=1+q(n,n-1)④m<n时： n的m划分有包含m和不包含m两个部分。

其中包含m的部分⽤集合可表⽰为{m, {x1, x2, x3, 4,…, xk}}(其中x1+x2+……+xk=n-m)【详解见图1】，这部分的划分数为q(n-m, m)；⽽不包含m的划分中，最⼤值不能为m，故划分数就等于q(n, m)。

所以在m<n时整数n的划分数为：q(n, m)=q(n, m-1)+q(n-m, m)。

【图1：ipad坏了，⼀时找不到纸，后⾯再补吧。

】递归求整数划分：1int q(int n, int m){2if(m==1){3return1;4 }5else if(m>n){6return q(n,n);7 }8else if(m==n){9return q(n,n-1)+1;10 }11else if(m<n){12return q(n-m, m)+q(n,m-1);13 }14 }。