递归算法及经典案例
递归是程序设计中的⼀种算法。⼀个过程或函数直接调⽤⾃⾝或通过其他的过程或函数调⽤语句间接地调⽤⾃⼰的过程或函数，称为递归过程或函数。
递归是较难理解的算法之⼀。简单地说，递归就是编写这样⼀个特定的过程，该过程中有⼀个语句⽤于调⽤过程⾃⾝。
好了，不多说了，看⼏个案例吧！
案例1：利⽤递归调⽤⼿段编程计算N!。
template <typename T>
T find(T n)  //递归函数
{
if (n == 1)
{
return 1;
}
else
{
return find(n - 1)*n;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
编程递归函数int n;
cout << "Please input n:" << endl;
cin >> n;
cout << "n! = " << find(n) << endl;
return 0;
}
案例2：试⽤递归的⽅法写⼀个计算斐波那契数列的通项f(n)，已知f1=1,f2=1，以后每项都是前两项的和。
template <typename T>
T f(T n)  //递归函数
{
if (n == 1 || n == 2)
{
return 1;
}
else
{
return f(n - 1) + f(n - 2);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int n;
cout << "Please input n:" << endl;
cin >> n;
cout << "n! = " << f(n) << endl;
return 0;
}
案例3：⼀个射击运动员打靶，靶⼀共有10环，连开10打中90环的可能性有多少种？
如果⽤⾮递归的⽅法实现，可以⽤10个循环语句来表⽰程序，代码如下：
for(i1=0;i1<10;i1++)
{
for(i2=0;i2<10;i2++)
{
...
if(i1+...+i9==90)
Print();
...
}
}
上⾯的代码可以解决问题，但是时间复杂度和空间复杂度⽆疑是很⾼的。
#include "stdafx.h"
#include <iostream>
using namespace std;
int sum = 0;
int socre[10];
//输出每次射击打中的环数
void Output()
{
for (int i = 0; i < 10;i++)
{
cout << socre[i] << "\t";
}
cout << endl;
sum++;
}
//统计满⾜条件的次数
template <typename T>
void Compute(T Sum_Socre, T n)
{
if (Sum_Socre < 0 || Sum_Socre > (n + 1) * 10)//次数n为0-9
return;
if (n == 0)
{
socre[n] = Sum_Socre;
Output();
return;
}
for (T i = 0; i <= 10;i++)
{
socre[n] = i;
Compute(Sum_Socre - i, n - 1);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
Compute(90, 9);
cout << sum << endl;
return 0;
}
案例4：⼋皇后问题。该问题是19世纪著名的数学家⾼斯1850年提出：在8×8格的国际象棋盘上摆放8个皇后，使不能互相攻击，即任意两个皇后都不能 处于同⼀⾏、同⼀列或同⼀斜线上，问有多少种摆法。
算法解析：
数组a、b、c分别⽤来标记冲突，a数组代表列冲突，从a[0]-a[7]代表第0列到第7列。如果某列上已有皇后，则为1，否则为0.
数组b代表主对⾓线冲突，为b[i-j+7]，即从b[0]-b[14]。如果某条主对⾓线上已经有皇后，则为1，否则为0.数组c代表从对⾓线冲突，为b[i+j]，即从c[0]-b[14]。如果某条从对⾓线上已经有皇后，则为1，否则为0.