在此幻灯片中，将研究许多列子，以 此来说明递归可以应用在多种情况下，同 时还会讨论递归方法的优势和劣势。
返回目录
2 对数列求和
※许多数学函数都是使用递归来定义的。我们首先从简单的例子研究起:
例：编写一个递归的方法来计算下面的级数；
m(i)=1/3+2/5+3/7+4/9+5/11+6/13+…i/(2i+1).
3 背包问题
递归算法：
bool knap(m,n) {
计科121404219 汤鑫 计科121404101 白钢
2014/09/18
引言
数列 求和
纵向显 示整数
背包 问题
字符串 排列
最大公约数
总结
引言
递归是一种方法（函数）调用自己的 编程技术，它在定义自身的同时又出现了 对自身的引用，有点类似于我们高中学的 的数学归纳法。用递归的目的在于解决一 种常见问题，即子任务不过是开始试图解 决的相同问题的一个较简单版本。
3 背包问题
现在将背包问题复杂化：一个背包容纳的物品最大质量为m, 现有n件物品，质量为m1,m2,… ,mn,均为正整数。要求从中 挑选若干件，使背包质量之和正好为m。
设用knap(m,n)来表示此问题。有解为true,否则为false。
3 背包问题
先考虑将物品mn放入背包的情况：
knap(m,n) = *若mn = m , 则knap(m,n) ← true *若mn > m,则knap(m,n) ← knap(m,n-1) *若mn < m， 则knap(m,n) ← knap(m,n-1) ＋knap(m-mn,n-1)
11,5
// Target=9, 5 is to small, no more items
8
// Target=20, 8 is to small
8,7
// Target=12, 7 is to small
8,7,6
// Target=5, 6 is to big8,7,5
8,7,5
// Target=5, 5 is right.
3 背包问题
分析：
1、如果选择的数据项的重量总和符合目标重量，工作就完成了。 2、从选择第一个数据项开始，剩余的数据项的加和必须符合背包 的目标重量减去第一个数据项的重量：这是一个新的目标重量。 3、逐个地试每种剩余数据项组合的可能性，但是，注意并不需要 去试所有的组合，因为只要数据项的和大于目标重量的时候，就 停止添加数据项。 4、如果没有组合合适的话，放弃第一个数据项，并且从第二个数 据项开始再重复一遍整个过程。 5、继续从第三个数据项开始，如此下去，直到试过所有组合，这 时就知道有没有解决方案。
2 对数列求和
由题可知a(i)=i/(2i+1)，要求a(i)就需要知道a(i-1)，由此可推，只要知道a(1)就可以 求a(i)。这里用递归方法就可以很简单的求解。
i
计算
1
1/3
2
1/3+2/5
3
11/15+3/7
4
122/105+4/9
5
506/315+5/11
6
7141/3465+6/13
… ……
3 背包问题
一个递归的程序能选择 第一个数据项，并且， 如果这个数据项比目标 重量小，程序可以用一 个新的目标值来调用自 身以继续试探剩余数据 项的和。
IHale Waihona Puke ems:11,8,7,6,5*********************************
11
// Target=20, 11 is to small
6/2= 3 ……} 0
3/2= 1 …… 1
当最后n=0时即可结束递归
1/2= 0 …… 1
返回目录
3 背包问题
例：试图将不同重量的数据项房入背包中，以使背包最
后达到指定的总重量。 如：背包精确地承重20磅，并且有5个可以选择放入的数据 项，它们的重量分别为11磅、8磅、7磅、6磅和5磅。对于选 择放入的数据项数量不大时，我们通过观察就可以解决这个 问题，只需放入8、7、5磅的数据项即可。 可是当背包所承受的总重量和数据项的重量过大时，我们需 要借用计算机来解决问题。
十进制转二进制
例：编写一个递归的方法，将一个整型十进制数转换为
一个二进制数。
分析：平常我们将p十ub进lic制st数atnic转vo化id成to二Bi进na制ry(数int时n，um是){将n不断除2， 然后所得的余数，从下if往(nu上m读/2取==0。){//此时已经计算到了结束
例如97：97/2=48……1} System.out.print(num%2); 48/2=24……0else{ 24/2=12……0 toBinary(num/2);//向下继续计算 System.out.print(num%2); 12/2= 6 ……0}
i
m(i-1)+i/(2i+1)
m(i) 1/3 11/15 122/105 506/315 7141/315 113623/45045 …… m(i）
2 对数列求和
边界
由表可知递归方程：
条件
1/3，i=1;
m(i)=
递归方程
“边界条件”是递归的 必要条件之一（它是递 归运算的出口）：另一 个条件是递归体,前者 确定递归到何时结束,
11,8
// Target=9, 8 is to small
11,8,7
// Target=1, 7 is to big
11,8,6
// Target=1, 6 is to big
11,8,5
// Target=1, 5 is to big, no more items
11,7
// Target=9, 7 is to small
11,7,6
// Target=2, 6 is to big
11,7,5
// Target=2, 5 is to big, no more items
11,6
// Target=9, 6 is to small
11,6,5
// Target=3, 5 is to big, no more items
m(i-1)+i/(2*i+1).
后者确定递归求解时的
所以，计算sequence_m(i)的算法可以简单如下：递推关系。
if(i==1)
return 1/3;
else
return sequence_m(i-1)+i/(2*i+1);
递归
现在大家应该对递归方法有了初步的了解 ， 可以开始用递归解决简单问题了。