算法设计及分析递归算法典型例题

递归算法及经典例题详解
1.什么是递归
递归简单来说就是在运行过程中不断调用自己，直到碰到终止条件，返回结果的过程。

递归可以看作两个过程，分别是递和归。

递就是原问题把要计算的结果传给子问题；归则是子问题求出结果后，把结果层层返回原问题的过程。

下面设一个需要经过三次递归的问题，为大家详细看一下递归的过程：当然，现实中我们遇到递归问题是不会按照图中一样一步一步想下来，主要还是要掌握递归的思想，找到每个问题中的规律。

2.什么时候使用递归
递归算法无外乎就是以下三点：1.大问题可以拆分为若干小问题2.原问题与子问题除数据规模不同，求解思路完全相同3.存在递归终止条件
而在实际面对递归问题时，我们还需要考虑第四点：
当不满足终止条件时，要如何缩小函数值并让其进入
下一层循环中
3.递归的实际运用（阶层计算）
了解了大概的思路，现在就要开始实战了。

下面我们来看一道经典例题：
求N的阶层。

首先按照思路分析是否可以使用递归算法：
1.N！可以拆分为（N-1）！*N
2.（N-1）！与N！只有数字规模不同，求解思路相同
3.当N=1时，结果为1，递归终止
满足条件，可以递归：
publicstaticintFactorial(int num){if(num==1){return num;}return num*Factorial(num-1);}
而最后的return，便是第四步，缩小参数num的值，让递归进入下一层。

一般来说，第四步往往是最难的，需要弄清该如何缩
小范围，如何操作返回的数值，这一步只能通过不断
地练习提高了（当然如果你知道问题的数学规律也是
可以试出来的）。

递归算法例子1. 哎呀，你知道计算阶乘吧！比如说 5 的阶乘就是5×4×3×2×1，这用递归算法就很合适呀！就像你一层一层地剥开洋葱一样，先计算 5 的阶乘，它又调用 4 的阶乘，一直这样递归下去，直到计算到 1 的阶乘！是不是很神奇啊？2. 嘿，你想想画一棵树，从树干开始不断长出树枝，这和递归算法多像呀！比如计算树的节点数量，一个节点会有子节点，然后子节点又有它的子节点，这就是在不断地递归呀！就像不停地探索未知一样，有趣吧？3. 哇哦，斐波那契数列知道吧！1，1，2，3，5，8 这样的，它用递归算法简直绝了啊！前两个数相加得到后面一个数，每次计算都要依靠前面的结果，这不就是递归在发挥神奇作用嘛！你说棒不棒？4. 嘿呀，拼图游戏玩过吧！当你一片片去组合的时候，其实也有点像递归算法呢！从局部到整体，一点点拼凑起来，这和递归的层层递进不是很像吗？比如要找出完整图案，就需要不断递归探索各个部分呀！5. 呐，汉诺塔游戏了解一下呀！要把盘子从一个柱子移到另一个柱子，这过程中就是递归在帮忙呢！每一步的移动都像是在打开一个新的递归之门，让整个过程充满挑战和乐趣，你难道不想试试吗？6. 哦哟，走迷宫的时候是不是感觉很奇妙？递归算法在这当中也能大显身手哦！比如找到走出迷宫的路径，就是不断尝试，不断递归，就像在黑暗中寻找光明一样刺激，不是吗？7. 嘿，文件系统的目录结构见过吧！从根目录到子目录，再到更下一级的目录，这多像递归呀！就像不断深入一个神秘的世界，每一次递归都是一次新的发现，是不是很有意思呢？8. 哇，你想想搜索一个大的数据集，用递归算法来查找特定的元素，那感觉就像是大海捞针，但又充满希望！每一次递归都是一次新的尝试，就像在茫茫人海中寻找那个特别的人一样，会带来惊喜哦！9. 总之呢，递归算法真的是无处不在，非常神奇！它能让复杂的问题变得简单有趣，能让我们看到问题的本质和内在联系。

递归算法典型例题数楼梯递归算法是一种常用的算法思想，它通过将问题分解为更小的子问题来解决复杂的计算任务。

在本文中，我们将探讨递归算法的一个典型例题——数楼梯。

问题描述：假设有n级楼梯，每次可以选择爬1级或2级，问有多少种不同的方式可以爬到楼梯的顶部。

解题思路：我们可以使用递归算法来解决这个问题。

假设f(n)表示爬到第n级楼梯的不同方式数目，那么可以得到以下递推关系：f(n) = f(n-1) + f(n-2)其中，f(n-1)表示从第n-1级楼梯爬1级到达第n级楼梯的方式数目，f(n-2)表示从第n-2级楼梯爬2级到达第n级楼梯的方式数目。

因为每次只能选择爬1级或2级，所以到达第n级楼梯的方式数目等于到达第n-1级楼梯的方式数目加上到达第n-2级楼梯的方式数目。

基本情况：当n=1时，只有一种方式可以到达第1级楼梯，即爬1级。

当n=2时，有两种方式可以到达第2级楼梯，即爬1级+1级或者直接爬2级。

递归算法实现：根据上述递推关系和基本情况，我们可以编写递归算法来解决这个问题。

```pythondef climb_stairs(n):if n == 1:return 1elif n == 2:return 2else:return climb_stairs(n-1) + climb_stairs(n-2)```测试与优化：我们可以通过调用climb_stairs函数来测试算法的正确性和效率。

```pythonn = 5result = climb_stairs(n)print("爬到第{}级楼梯的不同方式数目为：{}".format(n, result))```运行结果为：爬到第5级楼梯的不同方式数目为：8从结果可以看出，爬到第5级楼梯的不同方式数目为8，符合预期。

然而，上述递归算法存在一个问题，即重复计算。

在计算f(n)时，需要先计算f(n-1)和f(n-2)，而在计算f(n-1)时，又需要计算f(n-2)。

算法设计与分析基础习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。

数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。

故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[] 4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty. (―lazy deletion ‖)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。

关于递归与递推的那七道题递归与递推是动态规划最底层的东西，掌握好它对于彻底的理解动规是至关重要的，这次做的题不难，但是它很能锻练人的思维，每一道题都有多种解法。

只要静下心来想，一般人都能做出来，而在做题的过程中，你会有很大的收获。

1、一只小蜜蜂...题目是这样的，有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。

请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。

对于这种题目，我们首先得找出蜂房之间的关系，如从1只能走到2和3，从2只能走到3和4，从3只能走到4和5……，因此我们可以得到它们的递推关系：f[a] = f[a+1]+f[a+2]；下面我们再来找出口，把这个问题化简，即当a与b相邻时(a+1=b 或a+2=b)，f[a] = 1，所以这个问题可以解决了。

它就是一个递归，遇到b就结束。

为了减少重复访问，我们可以用记忆化搜索来提高效率。

这个题也可以顺着来推，即从a到a有0条路线，从a到a+1有1条路线,从a 到a+2有1条路线，而a+3的路线条数来源于a+1和a+2的路径条数。

f[a] = 0;f[a+1] = 1;f[a+2] = 1;f[a+3] = f[a+1]+f[a+2];……f[b] = f[b-1]+f[b-2];由上面的式子就可以看出，它就是一个菲波拉契数列。

2、LELE的RPG难题题目描述：有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.以上就是著名的RPG难题.解法一：这个题目经过同学们的讨论，得出了三种解法。

我所用的方法还是搜索，我们先不考虑它的限制条件，把第一个格子看成是树的根，那么总共可以建成三棵树，每一棵树的结点都有三个孩子。

我们的目标就是要统计这三棵树中分别从根结点走到叶子结点的总的路径条数。

然后把限制条件加上，把不符合要求的路径去掉，即可得出最终的结果。

递归的经典例子
1. 算数学题的时候啊，像计算一个数的阶乘，这就是一个递归的经典例子呀！比如说计算 5 的阶乘，不就是 5 乘以 4 的阶乘嘛，而 4 的阶乘又等于 4 乘以 3 的阶乘，依次类推，这多有意思啊！
2. 还有走迷宫呢，你想想，当你在迷宫里遇到岔口，你选择一条路走，然后又遇到岔口，又继续选择，这不就跟递归很像嘛！你不断地进入更小的问题去探索，直到找到出口，这难道不是很神奇吗？
3. 画树也可以用递归呀！先画一个树干，然后树干上又分出树枝，每个树枝又可以当作新的树干去继续分树枝，这不就跟递归的过程一样嘛，哇塞，这样就能画出一棵复杂又漂亮的树啦！
4. 你知道汉诺塔游戏不？那就是典型的递归例子哟！要把盘子从一个柱子移到另一个柱子，不就得不断地用递归的方法去解决嘛，天啊，真是好烧脑又好有趣！
5. 再来说说我们电脑里的文件系统，那也是递归的体现呀！文件夹里有子文件夹，子文件夹里还有子文件夹，就这么一层层下去，像不像递归在大展身手呢？
6. 回忆一下我们看电影的时候，很多故事里不是也有类似递归的情节嘛！主角解决一个问题又引出新的问题，然后一直这么循环，这也可以说是一种故事里的递归呀，多有意思的发现呀！
总之，递归在生活中无处不在，它就像一把神奇的钥匙，能打开很多复杂问题的大门，给我们带来惊喜和挑战！。

数据结构（⼗⼆）递归的应⽤--汉诺塔问题 ⼀、汉诺塔问题描述 设有三根标号为A，B，C的柱⼦，在A柱⼦上放着n个盘⼦，每个逗⽐下⾯的略⼩⼀点，要求把A上的盘⼦全部转移到C上，移动的规则是：①⼀次只能移动⼀个盘⼦；②移动过程中⼤盘⼦不能放在⼩盘⼦上⾯；③在移动过程中盘⼦可以放在A，B，C的任意⼀个柱⼦上。

⼆、⽤递归⽅法求解n个盘⼦的汉诺塔问题的基本思想 ⼀个盘⼦的汉诺塔问题可以直接移动（递归出⼝）。

n个盘⼦的汉诺塔问题可递归表⽰为：⾸先把上边的n-1个盘⼦从A移动B，然后把最下边的⼀个盘⼦从A移到C（直接求解），最后把移到B的n-1个盘⼦移到C。

三、⽤递归求解汉诺塔问题的实现 1.算法实现package bigjun.iplab.HanoiTowers;public class HanoiTowers {public static void hTowers(int n, char form, char to, char via) {// 递归出⼝，n=1只有⼀个盘⼦时，直接从A移到Cif (n == 1) {System.out.println("移动盘⼦1从" + form + "到" + to);return;}// 将n-1个盘⼦从A借助C移到BhTowers(n - 1, form, via, to);System.out.println("移动盘⼦" + n + "从" + form + "到" + to);// 将n-1个盘⼦从B借助A移到ChTowers(n - 1, via, to, form);}public static void main(String[] args) {// 将4个盘⼦从A借助B移到ChTowers(4, 'A', 'C', 'B');}} 2.输出移动盘⼦1从A到B移动盘⼦2从A到C移动盘⼦1从B到C移动盘⼦3从A到B移动盘⼦1从C到A移动盘⼦2从C到B移动盘⼦1从A到B移动盘⼦4从A到C移动盘⼦1从B到C移动盘⼦2从B到A移动盘⼦1从C到A移动盘⼦3从B到C移动盘⼦1从A到B移动盘⼦2从A到C移动盘⼦1从B到C 3.结合输出分析代码执⾏过程将4个盘⼦从A借助B移到C可分为如下过程：将3个盘⼦从A借助C移到B，然后再将1个盘⼦从A移到C，最后把3个盘⼦从B移到C将3个盘⼦从A借助C移到B可分为如下过程： 将2个盘⼦从A借助B移到C，然后再将1个盘⼦从A移到B，最后把2个盘⼦从C移到B将2个盘⼦从A借助B移到C可分为如下过程： 将1个盘⼦从A移到B，然后将1个盘⼦从A移到C，最后将1个盘⼦从B移到C 四、算法分析 递归算法把移动n个盘⼦的汉诺塔问题分解为移动n-1个盘⼦的汉诺塔问题，把移动n-1个盘⼦的问题分解成n-2个盘⼦的问题，...，把移动两个盘⼦的汉诺塔问题分解成移动⼀个盘⼦的汉诺塔问题。

算法递归典‎型例题实验一：递归策略运‎用练习三、实验项目1．运用递归策‎略设计算法‎实现下述题‎目的求解过‎程。

题目列表如‎下：（1）运动会开了‎N天，一共发出金‎牌M枚。

第一天发金‎牌1枚加剩‎下的七分之‎一枚，第二天发金‎牌2枚加剩‎下的七分之‎一枚，第3天发金‎牌3枚加剩‎下的七分之‎一枚，以后每天都‎照此办理。

到了第N天‎刚好还有金‎牌N枚，到此金牌全‎部发完。

编程求N和‎M。

（2）国王分财产‎。

某国王临终‎前给儿子们‎分财产。

他把财产分‎为若干份，然后给第一‎个儿子一份‎，再加上剩余‎财产的1/10；给第二个儿‎子两份，再加上剩余‎财产的1/10；……；给第i个儿‎子i份，再加上剩余‎财产的1/10。

每个儿子都‎窃窃自喜。

以为得到了‎父王的偏爱‎，孰不知国王‎是“一碗水端平‎”的。

请用程序回‎答，老国王共有‎几个儿子？财产共分成‎了多少份？源程序：（3）出售金鱼问‎题：第一次卖出‎全部金鱼的‎一半加二分‎之一条金鱼‎；第二次卖出‎乘余金鱼的‎三分之一加‎三分之一条‎金鱼；第三次卖出‎剩余金鱼的‎四分之一加‎四分之一条‎金鱼；第四次卖出‎剩余金鱼的‎五分之一加‎五分之一条‎金鱼；现在还剩下‎11条金鱼‎，在出售金鱼‎时不能把金‎鱼切开或者‎有任何破损‎的。

问这鱼缸里‎原有多少条‎金鱼？（4）某路公共汽‎车，总共有八站‎，从一号站发‎轩时车上已‎有n位乘客‎，到了第二站‎先下一半乘‎客，再上来了六‎位乘客；到了第三站‎也先下一半‎乘客，再上来了五‎位乘客，以后每到一‎站都先下车‎上已有的一‎半乘客，再上来了乘‎客比前一站‎少一个……，到了终点站‎车上还有乘‎客六人，问发车时车‎上的乘客有‎多少？（5）猴子吃桃。

有一群猴子‎摘来了一批‎桃子，猴王规定每‎天只准吃一‎半加一只（即第二天吃‎剩下的一半‎加一只，以此类推），第九天正好‎吃完，问猴子们摘‎来了多少桃‎子？（6）小华读书。

第一天读了‎全书的一半‎加二页，第二天读了‎剩下的一半‎加二页，以后天天如‎此……，第六天读完‎了最后的三‎页，问全书有多‎少页？（7）日本著名数‎学游戏专家‎中村义作教‎授提出这样‎一个问题：父亲将25‎20个桔子‎分给六个儿‎子。

算法递归典型例题实验一：递归策略运用练习三、实验项目1运用递归策略设计算法实现下述题目的求解过程。

题目列表如下：(1)运动会开了N天，一共发岀金牌M枚。

第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。

到了第N天刚好还有金牌N枚，到此金牌全部发完。

编程求(2)国王分财产。

某国王临终前给儿子们分财产。

他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10;给第二个儿子两份，再加上剩余财产的1/10 ;……；给第i个儿子i份，再加上剩余财产的1/10。

每个儿子都窃窃自喜。

以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。

请用程序回答，老国王共有几个儿子？财产共分成了多少份？源程序：(3)岀售金鱼问题：第一次卖岀全部金鱼的一半加二分之一条金鱼；第二次卖岀乘余金鱼的三分之一加三分之一条金鱼；第三次卖岀剩余金鱼的四分之一加四分之一条金鱼；第四次卖岀剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在岀售金鱼时不能把金鱼切开或者有任何破损的。

问这鱼缸里原有多少条金鱼？(4)某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？(5)猴子吃桃。

有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只(即第二天吃剩下的一半加一只，以此类推) ，第九天正好吃完，问猴子们摘来了多少桃子？(6)小华读书。

第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？(7)日本著名数学游戏专家中村义作教授提岀这样一个问题：父亲将2520个桔子分给六个儿子。

分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7 给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。

递归算法实例忘记关窗子给冷风吹醒了，额！前段时间研究PHP，关于递归有个例题“馋嘴猴子”。

说有只猴子弄到了一堆桃子，它第一天吃了这堆的一半，还觉得不过瘾，出门的时候又吃了一个，第二天吃了剩下的桃子的一半再加一个，每天都这样，第十天准备吃的时候，发现桃子只剩一个了，问最初一共有多少个桃子。

问题并不复杂，但是要用倒着推的方式，第十天的桃子数量1也就是第九天剩下的数量，设第九天桃子数量为X,则有等式：X/2-1=1，解得:X=4。

以此类推可以算出最初的桃子数量。

用编程的方式解决这个问题，有两种推导方式，“迭代”和“递归”。

今天主要说说编程中递归，递归说白了就是函数自己调用自己，这种流程控制方法和“迭代”一样，都是用在代码执行步进中，后一步的计算结果当做前一步计算参数的时候。

“递归”的关键是出口，就是结束递归的条件，条件设置不合适，容易死循环。

来个简单的例子----阶乘，阶乘就是自然数从1乘到自己本身，比如3的阶乘，就是1x2x3=6。

用VBA实现，按正常的流程做法应该是：Function Factorial0(ByVal num As Integer)Dim i As LongFactorial0 = 1For i = 1 To numFactorial0 = Factorial0 * iNext iEnd Function这么写也无可厚非，比较容易理解，用递归写阶乘代码是下面这样的：Function Factorial(ByVal num As Integer)If num = 1 Then '这里设置的是递归的出口，NUM是1就结束Factorial = 1ElseFactorial = num * Factorial(num - 1)'这里是重点，自己调用自己，变量NUM减1End IfEnd Function接着上面“馋嘴猴子”的问题，用递归解决代码如下：Function peach2(ByVal k As Integer)Dim ii = 1If i = k Then '设置递归出口，当天数等于K则结束peach2 = 1Elsepeach2 = 2 * (peach2(i + 1) + 1)'递归调用自身的部分i = i + 1End IfEnd Function下面是“迭代”的代码，我也放上来，对比一下：Function peach(ByVal k As Integer)Dim i As Integer, res As Longres = 1For i = k - 1 To 1 Step -1res = 2 * (res + 1)peach = res * 2Next iEnd Function。

背包问题解析（⼆）-递归算法⼀、题⽬:有N件物品和⼀个容量为V的背包。

第i件物品的重量是w[i]，价值是v[i]。

求解将哪些物品装⼊背包可使这些物品的重量总和不超过背包容量，且价值总和最⼤。

⼆、递归⽅法：⾸先对于每个物品，我们的选择只有两个：放或者不放。

我们将所有的可能都穷举出来，就可以得到下⾯这个树状图（只画了前四个结点）：所以对于每⼀个⼦问题，由于前⾯的⼦问题已被解决，因此我们都只需要做两个选择：放，还是不放。

假设我们已经知道了前i−1个物品放⼊背包的最优⽅案F(i−1,v i−1 )，那么对于第i个物品要放⼊背包就有三种情况：1、若物品的体积c i ⼤于背包剩余的容量v i−1 ，那么只能丢弃这个物品：F(i,vi)=F(i−1,vi−1)2、否则就有两种选择：（1）、不放第i个物品：F(i,vi)=F(i−1,vi−1)（2）、放第i个物品：F(i,vi)=wi+F(i−1,vi−1−ci)要从这两个⽅案中选择总价值最⼤的，所以：三、python代码实现如下：def rec_bag(c, w, v, i=0):'''param c: 物品体积param w: 物品价值param v: 当前背包剩余容量param i: 当前物品编号return: 背包装下物品的最⼤价值'''if i > len(c)-1:return 0elif v <= 0: #体积不能为负return 0elif v > 0:if c[i] <= v:A = w[i] + rec_bag(c, w, v-c[i], i+1)B = rec_bag(c, w, v, i+1)res = max(A, B)#两种⽅案中选最优的那个并返回else:res = rec_bag(c, w, v, i+1)#物品体积⼤于背包容量，直接返回return resa=rec_bag([2,3,4,5],[3,4,5,6],8,0)print(a)四、算法分析：递归⽅法最⼤的缺点就在于有较多重复的计算，通过上⾯的树状图可以知道，递归会遍历这棵树的所有结点，所以它的时间复杂度为：O(2 n )O(2n)，指数阶的时间复杂度对于计算机来说简直就是灾难！有没有什么办法减少这些重复的计算呢？这就是接下来要说的动态规划，它可以通过存储已经计算出来的结果来减少重叠⼦问题。

【算法分析】递归算法的⼏个经典例⼦例⼀：整数划分问题 将正整数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 }。

递归算法经典题目递归算法是一种非常强大的编程技术，它能够解决一些复杂的问题，将它们分解为更小的子问题。

以下是一些经典的递归算法题目：1. 斐波那契数列：这是一个经典的递归问题，斐波那契数列中的每个数字都是前两个数字的和。

例如，0, 1, 1, 2, 3, 5, 8, 13, 21... 编写一个函数来计算斐波那契数列中的第n个数字。

2. 阶乘：阶乘是一个数的所有小于及等于该数的正整数的乘积。

例如，5的阶乘（记作5!）是5 4 3 2 1 = 120。

编写一个函数来计算一个数的阶乘。

3. 二分搜索：二分搜索是一种在排序数组中查找特定元素的搜索算法。

编写一个函数，该函数使用二分搜索在给定的排序数组中查找特定的元素。

4. 回溯算法：回溯算法用于解决决策问题，例如八皇后问题。

在这个问题中，我们需要在一个8x8棋盘上放置8个皇后，使得任何两个皇后都不在同一行、同一列或同一对角线上。

编写一个使用回溯算法解决八皇后问题的函数。

5. 合并排序：合并排序是一种分治算法，它将一个大的列表分成两个较小的子列表，对子列表进行排序，然后将它们合并成一个已排序的列表。

编写一个使用递归实现合并排序的函数。

6. 快速排序：快速排序也是一种分治算法，它选择一个"基准"元素，然后将所有比基准小的元素放在其左边，所有比基准大的元素放在其右边。

然后对左右两个子列表进行快速排序。

编写一个使用递归实现快速排序的函数。

7. 深度优先搜索（DFS）：这是一种用于遍历或搜索树或图的算法。

这个算法会尽可能深地搜索树的分支。

当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

这一过程一直进行到已发现从源节点可达的所有节点为止。

如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

编写一个使用递归实现深度优先搜索的函数。

这些题目都可以帮助你理解和应用递归算法。