第六章 递归
本童重点
三角数字
阶乘
变位字
递归的二分查找
汉诺塔
归并排序
消除递归
一些有趣的递归应用
三角数字
据说毕达哥拉斯理论家，发现了在数字序列 1 ， 3 ，
6 ， 10 ， 15 ， 21 ， ．．．中有一种奇特的联系。
这个数列中的第 n 项是由第 n—1 项加 n 得到的。
这个序列中的数字被称为三角数字，因为它们可以
被形像化地表示成对象的一个三角形排列，如图 6 ．
1 中小方块所示。
使用循环查找第 n 项
假设想要在这个数列中找到某任意项，第 n 项的值，
比如说第 4 项 ( 其值为 10) 。你会如何计算它呢？
看图 6 ． 2 ，可以判定任何项的值都可以通过把所
有竖直列上的小方块加起来而得到。
这栏为 1
这栏为 2
这栏为 3
这栏为 4
图 6 ． 2 按列分割的三角数宇
下面的 triangle(] 方法使用这种基于列的方法来找到一个三角数
字。
int triangle(int n)
{
int total = 0;
while(n>0) //until n is 1
{
total = total +n; //add n(column height) t
o total
--n; //dec
rement column height
}
return total;
}
使用递归查找第 n 项
循环的方法好象是非常易懂的、但是还可以通过另外一种方式来看这个问题。
第 n 项的值可以被看成只是两个部分的和，而不是被看作整个序列的和。
它们是：
1 ．第一列 ( 最高的一列 ) ，它的值为 n ．
2 ．所有剩余列的和。
如图 6 ． 3 所示。
所有其他的和为
6
这栏为 4
图 6 ． 3 列加上三角形求三角数
字
