在数学与计算机科学中，递归(recursion)是指一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大减少了程序的代码量。递归的能力在于用有限的语句定义对象的无限集合。一个递归问题可分为递推和回归两个阶段。在递推阶段，把较复杂问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解；在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。

只有同时满足下面三个条件的问题，才能用递归解决。

(1) 一个问题可以转化为一个与原问题相似的、规模较小的子问题来求解。比如，在n的阶乘的计算中，将n的阶乘的问题转化为n-1的阶乘乘以n，此问题便可解决。

(2) 这个问题与分解之后的子问题，除数据规模不同，求解思路完全一样。比如，n的阶乘问题中，求解n的阶乘的思路，和求解n-1的阶乘的思路是一模一样的。

(3) 存在递归终止条件。

把问题分解为子问题，再把子问题分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。比如，n的阶乘问题中，0或1的阶乘为1，也就是f(1)=1，f(0)=1,这就是递归的终止条件。

递归是很多算法实现的基础，是程序设计中的一种重要思想和机制，如分治、深度优先搜索、动态规划等算法中均用到递归思想。

01、汉诺塔问题

汉诺（Hanoi）塔问题是一个经典的运用递归方法解决问题的例子。

问题描述:

汉诺塔是一个发源于印度的益智游戏，也叫河内塔。相传它源于印度神话中的大梵天创造的三根金刚柱，一根柱子上叠着上下从小到大64个黄金圆盘。大梵天命令婆罗门将这些圆盘按从小到大的顺序移动到另一根柱子上，其中大圆盘不能放在小圆盘上面。当这64个圆盘移动完的时候，世界就将毁灭。

那么，好多人会问64个圆盘移动到底会花多少时间？古代印度距离现在已经很远，这64个圆盘还没移动完么？我们通过计算看完成这个任务到底要多少时间？计算结果非常恐怖，移动圆盘的次数为2n-1，即18446744073709551615，假设移动一次圆盘用时一秒，一年为31536000秒。那么，18446744073709551615/31536000约等于584942417355年，即约为5850亿年。目前太阳寿命约为50亿年，太阳的完整寿命大约100亿年。所以，整个人类文明都等不到移动完整圆盘的那一天。很多人对汉诺塔的解法产生了兴趣。从一阶汉诺塔到N阶汉诺塔它们是否有规律性的算法？能否编程输出每一次移动的方法呢？这就是本例要解决的问题。

输入:

输入一个正整数n，表示有n个圆盘在第一根柱子上。

输出:

输出操作序列，格式为move t from x to y。每个操作一行，表示把x柱子上的编号为t的盘片挪到柱子y上。柱子编号为a，b，c，要用最少的操作把所有盘子从a柱子上转移到c柱子上。

输入样例:

3

输出样例:

move 1 from a to c
move 2 from a to b
move 1 from c to b
move 3 from a to c
move 1 from b to a
move 2 from b to c
move 1 from a to c

解题思路:

实现这个算法，可以简单分为以下三个步骤。

(1) 把第n-1个圆盘由a移到b。

(2) 把第n个圆盘由a移到c。

(3) 把第n-1个圆盘由b移到c。

从这里入手，加上上面数学问题解法的分析，不难发现，移动的步数必为奇数步。

(1) 第二步是把a柱子上剩下的一个盘子移到c柱子上。

(2) 第一步可以看成把a柱子上的n-1个圆盘借助c柱子移到b柱子上。

(3) 第三步可以看成把b上的n-1个圆盘借助a柱子移到c柱子上。

如3阶汉诺塔的移动: A→C,A→B,C→B,A→C,B→A,B→C,A→C。

参考程序:

#include <fstream>
#include <iostream>
using namespace std;
/ *将x柱子上编号为 t的圆盘移动到 柱子上 * /
void Move(int t,char x,char y) [cout<<"move "<<t<<" from "<<x<<" to "<<y<<endl;
/*将 n个圆盘从 a 柱子借助 b 柱子移到 c 柱子 * /
void Hannoi(int n,char a,char b,char c)
{
  if(n==1)
move(1,a,c)
Move(1,a,c); /* 若只有一个圆盘，则直接将该圆盘由 a 柱子移到 c 柱子 * /
else
{
Hannoi(n-1,a,c,b); / * 把 a 柱子上的 n-1个圆盘借助 c 柱子移到 b 柱子上* /
Move(n,a,c);  /*把 a 柱子上剩下的一个盘子移到 c 柱子上*/
Hannoi(n-1,b,a,c);  /*把b 柱子上的 n-1个圆盘借助 a 柱子移到 c 柱子上* /
 
}
})
 
 
int main()
int n;
scanf("%d",&n);
Hannoi(n,'a','b','c') ;
return 0;
}

02、木棒三角形

问题描述:

小A家里有很多长度不一的木棒，有一天他很无聊，摆弄这些木棒解闷。小A的数学学得很好，所以他想在这些木棒中挑出三根木棒组成一个直角三角形，当然，这可能有很多种选法，他还想挑出三根木棒组成一个面积最大的直角三角形。

输入:

输入有多组，每组输入包括两行，第一行输入一个n(0≤n≤100)，表示小A有n根木棒，接着一行有n个整数（n≤1000），表示木棒的长度（长度从小到大给出）。

输出:

输出面积最大的直角三角形的面积，且保留3位小数，若不能组成，则输出“My Good!”。

输入数据:

4
1 2 3 4
5
2 3 4 5 6
6
3 4 5 6 8 10
2
1 1

输出数据:

My Good!
6.000
24.000
My Good!

解题思路:

看到题目很容易想到如果求出从n根木棒中选出三根木棒的所有情况的解，那答案也就出来了。

现在的主要问题是怎么用程序枚举所有情况。我们知道直角三角形的三条边中斜边是最长的，题目给出一个“长度从小到大给出”的条件，这样我们可以依次枚举三角形中长度最短、第二长和最长的边，具体实现代码如下。

参考程序:

#include< stdio.h>
#include<stdlib.h>
int main()
{
int i,j,k;
double ans;
int n;
int len[110];
while(scanf(rd",&n)!=EOF)
{for(i = 1;i <= n;i++)scanf("%d",&len[i]); //存储木棒长度
ans = -1;
for(i = l;i <= n;i++){  //枚举最短木棒
for(j = i+l;j <= n;j++){ //枚举第二长的木棒
for(k = j+1;k <= n;k++){  //枚举最长的木棒
if(len[i]*len[i] + len[j]*len[j] == len[k]* len[k]){ //如果是直角三角形
if(0.5*len[i]*len[j] > ans) //取最优解
ans = 0.5*len[i]*len[j];
}
}
}
}
if(ans == -1)
printf("My Good! \n");
else
printf("%.3lf\n",ans);
}