本篇主要是圍繞著遞歸算法的概念、實(shí)質(zhì)、思想以及設(shè)計(jì)要素四個(gè)方向敘述，同時(shí)通過(guò)實(shí)例講解，促進(jìn)大家對(duì)遞歸算法的理解。

一、算法概念

遞歸算法是一種直接或者間接調(diào)用自身函數(shù)或者方法的算法。說(shuō)簡(jiǎn)單了就是程序自身的調(diào)用。

二、算法實(shí)質(zhì)

遞歸算法就是將原問(wèn)題不斷分解為規(guī)模縮小的子問(wèn)題，然后遞歸調(diào)用方法來(lái)表示

問(wèn)題的解。（用同一個(gè)方法去解決規(guī)模不同的問(wèn)題）

三、算法思想

遞歸算法，顧名思義就是有兩個(gè)大的階段：遞和歸，即就是有去（遞去）有回（歸來(lái)）。

遞去：將遞歸問(wèn)題分解為若干個(gè)規(guī)模較小，與原問(wèn)題形式相同的子問(wèn)題，這些子問(wèn)題可以用相同的解題思路來(lái)解決

歸來(lái)：當(dāng)你將問(wèn)題不斷縮小規(guī)模遞去的時(shí)候，必須有一個(gè)明確的結(jié)束遞去的臨界點(diǎn)（遞歸出口），一旦達(dá)到這個(gè)臨界點(diǎn)即就從該點(diǎn)原路返回到原點(diǎn)，最終問(wèn)題得到解決。

遞歸的圖解分析

四、遞歸算法的設(shè)計(jì)要素

遞歸思維是一種從下向上的思維方式，使用遞歸算法往往可以簡(jiǎn)化我們的代碼，而且還幫我們解決了很復(fù)雜的問(wèn)題。遞歸算法的難點(diǎn)就在于它的邏輯性，一般設(shè)計(jì)遞歸算法需要考慮以下幾點(diǎn):

（1）明確遞歸的終止條件

（2）提取重復(fù)的邏輯，縮小問(wèn)題的規(guī)模不斷遞去

（3）給出遞歸終止時(shí)的處理辦法

五、遞歸算法的經(jīng)典實(shí)例

（1）階乘

         n! = n * (n-1) * (n-2) * ...* 1(n>0)

//階乘
int recursive(int i)
{
	int sum = 0;
	if (0 == i)
		return (1);
	else
		sum = i * recursive(i-1);
	return sum;
}

（2）河內(nèi)塔問(wèn)題

（3）全排列

從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來(lái)，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。

如1,2,3三個(gè)元素的全排列為：

  1,2,3

  1,3,2

  2,1,3

  2,3,1

  3,1,2

  3,2,1

//全排列
inline void Swap(int &a,int &b)
{
	int temp=a;
	a=b;
	b=temp;
}
void Perm(int list[],int k,int m)
{
	if (k == m-1) 
	{
		for(int i=0;i<m;i++)
		{
			printf("%d",list[i]);
		}
		printf("n");
	}
	else
	{
		for(int i=k;i<m;i++)
		{
			Swap(list[k],list[i]); 
			Perm(list,k+1,m);
			Swap(list[k],list[i]); 
		}
	}
}

（4）斐波那契數(shù)列

斐波納契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、……

這個(gè)數(shù)列從第三項(xiàng)開(kāi)始，每一項(xiàng)都等于前兩項(xiàng)之和。

有趣的兔子問(wèn)題：

一般而言，兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來(lái)。如果所有兔子都不死，那么一年以后可以繁殖多少對(duì)兔子？

分析如下：

第一個(gè)月小兔子沒(méi)有繁殖能力，所以還是一對(duì)；

兩個(gè)月后，生下一對(duì)小兔子，總數(shù)共有兩對(duì)；

三個(gè)月以后，老兔子又生下一對(duì)，因?yàn)樾⊥米舆€沒(méi)有繁殖能力，總數(shù)共是三對(duì)；

……

依次類推可以列出下表：

//斐波那契
long Fib(int n)
{
	if (n == 0) 
		return 0;
	if (n == 1) 
		return 1;
	if (n > 1) 
		return Fib(n-1) + Fib(n-2);
}