再帰アルゴリズムと古典的なケース

再帰はプログラム設計におけるアルゴリズムである.1つのプロシージャまたは関数は、再帰プロシージャまたは関数と呼ばれる、または他のプロシージャまたは関数呼び出し文を介して間接的に独自のプロシージャまたは関数を呼び出す.
再帰は理解しにくいアルゴリズムの一つである.簡単に言えば、再帰は、プロシージャ自体を呼び出すための文を持つ特定のプロシージャを記述することである.
はい、あまり言わないで、いくつかのケースを見てみましょう.
ケース1:再帰呼び出し手段を用いてN!をプログラミング計算する.

template 
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)を書き、f 1=1,f 2=1が知られており、以降は各項が前の2項の和である.

template 
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:1人の射撃選手がターゲットを打って、ターゲットは全部で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 
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 
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つの皇后が置かれており、互いに攻撃できないようにしています.つまり、いずれの皇后も同じ行、同じ列、同じ斜線に置くことができません.何種類の振り方がありますか.
アルゴリズム解析:
配列a、b、cはそれぞれ衝突をマークするために用いられ、a配列は列衝突を表し、a[0]-a[7]は0列目から7列目を表す.ある列に皇后がある場合は1、そうでない場合は0.
配列bは、主対角線衝突を表し、b[i−j+7]、すなわちb[0]−b[14]である.ある主対角線に皇后がすでに存在する場合は1であり、そうでない場合は0である.
配列cは、対角線からの衝突、すなわちc[0]−b[14]を表す.対角線からすでに皇后がある場合は1、そうでない場合は0.