递归和数学归纳法
计算机就是数学的一个分支，不管你认不认同，你都会发现在编程的过程中，你能够发现很多的数学思维的闪现，就比如递归，递归可以让程序简化，与非递归比较，简单的递归函数省去了大段大段的代码，让人叹服不已，递归往往能体现设计者头脑的聪慧，但是递归的思想与数学又有什么相关呢？
本文将介绍递归与数学归纳法之间的联系，希望给读者一些启迪。
要说递归得先说，数学归纳法，想必每一个程序员在高中的时候就应该学习了数学归纳法，当我们需要去证明一个证明题时，很可能就要用到数学归纳法，数学归纳法的思想如下：
而递归利用的也是递推的原理，在整个程序中，反复实现的将是同一个原理。在这一点上，递归与数学归纳法本质是相同的。所以往往可以利用数学归纳法来设计递归的实现。计算机是数学应用的一个分支在这里体现的淋漓尽致。
首先可知当N=1时 N!=1
第二步可设当R(N)=N!，R(N+1)=(N+1)!
第三步，求R(N+1)与R(N)之间的关系。R(N)=N!，
而R(N+1)=(N+1)!=(N+1)*(N)*(N-1)*…*2*1=(N+1)*N!=(N+1)*R(N)
即：R(N+1)=(N+1)*R(N) =〉 R(N)=N*R(N-1)
现在根据这个公式草略地构造一个函数：
factorial (int N)
{
return N * factorial (N – 1) /* 递归部分 */
}
接下来补充截止部分，这一部分在整个过程中只使用一次，没有它，程序就将无限递归下去。可以说它是程序运行栈的栈顶，到了它，就开始一步步退栈了。
函数改为：
{
if (N == 1) return 1;
return N * factorial (N – 1) /* 递归部分 */
}
现在来总结设计递归程序的步骤：
一、用数学归纳法分析问题，根据数学归纳法的第一步得出截至部分。
二、根据数学归纳法的第三步来构造函数的递归部分。其实这个求解过程就是找出R(N)与R(N-1)的关系式。
现在利用总结出的方法做一个练习，比较经典的汉诺塔。
汉诺塔想必大家都知道：三个立柱（命名为from、temp、to，from为圆盘初始所在立柱、to是目标立柱），N个直径不相等的
圆盘，将圆盘从from上一个一个移动在to上，要求，每次只能移动一个圆盘，而且只能在三个立柱之间移动。不能出现大盘压小盘的情况。 首先用数学归纳法分析：
当只有一个
现在假设有N个圆盘在from上，而我们可以将这些圆盘最终按要求移动到to上（当然也可以移动到temp上）。
那么我们可以证明如果有N+1个时候，我们也可以将圆盘全部按要求移动到to上：
因为我们可以先将上面的N个移动到temp上（第二步已假设），再把剩下的最后一个移动到to上，再把temp上的移动到to上。按照我们总结过的递归函数设计步骤来设计程序：
首先，确定截至部分：当只有一个圆盘移动的时候，直接将它移动到to上。即：if (n == 1) move (n, from, to);
（这里的move函数意义是将n号圆盘，或者说初始状态下从上面数第n个圆盘，从from移动到to）
第二步确定递归部分，其实就是N+1与N的关系部分，就是红色字体部分。现在开始把文字转化为程序：
设Hanoi (int n, int from, int temp, int to)函数就是我们要求的汉诺塔实现函数，意义是将按直径递增摞在一起的n个圆盘从from按要求移动到to上，temp为辅助圆盘。
可写出代码：
Hanoi (n-1, from, temp); /*
move (n, from, to); /* 剩下的最后一个移动到to上 */
Hanoi (n-1, temp, to); /* 再把temp上的移动到to上 */
第二步完成，最后合成函数：
void
Hanoi (int n, int from, int temp, int to)
{
if (n == 1)
move (n, from, to);
else
{
move (n, from, to);
Hanoi (n-1, temp, to);
}
}
使用数学归纳法设计递归程序最大的好处就是可以使设计者摆脱对递推的顾虑。因为你设计的代码必定隐含着递推的步骤。直接根据你的分析文字转化为代码即可。
本文还有很多不足之处，欢迎读者指教。