前言

最近被函數(shù)遞歸困惱許久，今天就帶領(lǐng)大家一起探秘遞歸。

什么是遞歸

程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。

遞歸做為一種算法在程序設(shè)計(jì)語(yǔ)言中廣泛應(yīng)用。 一個(gè)過程或函數(shù)在其定義或說明中有直接或間接 調(diào)用自身的 一種方法，它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解， 遞歸策略 只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。

遞歸的主要思考方式在于：把大事化小。(這個(gè)想法很重要)

遞歸的兩個(gè)必要條件

1 存在限制條件，當(dāng)滿足這個(gè)限制條件的時(shí)候，遞歸便不再繼續(xù)。

2 每次遞歸調(diào)用之后越來越接近這個(gè)限制條件

為了更好的理解遞歸我將為大家分享幾到題目。

題解遞歸

在解題之前，我想剛剛接觸遞歸的小伙伴都會(huì)面臨，我知道遞歸是什么，但就是不會(huì)寫他或者說不理解怎么實(shí)現(xiàn)。為此大家可以參考我的解題三步驟。

步驟一：明確你的函數(shù)要實(shí)現(xiàn)什么功能。

在我看來，要想求解一個(gè)遞歸你肯定要知道你要實(shí)現(xiàn)一個(gè)什么功能，寫出一大概的函數(shù)出來。

//求n的階乘
int demand_factorial(int n)
{
}

在這個(gè)代碼中，我們明確了這個(gè)函數(shù)要求的是n的階乘，求階乘所所需要的參數(shù)。

步驟二：尋找遞歸結(jié)束的條件

遞歸就是在函數(shù)在不斷的調(diào)用自己，要想停下來，肯定是要有條件能讓他停下來，不然會(huì)一直調(diào)用自己而陷入死遞歸。就是說我們要找到一個(gè)參數(shù)為啥時(shí)，遞歸結(jié)束，之后直接把結(jié)果返回。請(qǐng)注意這個(gè)參數(shù)值我們必須明白，參數(shù)為何值的時(shí)候，函數(shù)的結(jié)果是什么。

對(duì)于上面那個(gè)例子，我們肯定明白n = 1時(shí)函數(shù)的結(jié)果為1。那么我們便可以這么寫。

//求n的階乘
int demand_factorial(int n)
{
	if (n == 1)
	{
		return 1;
	}
}

為什么說當(dāng)我們明確知道，n = 1時(shí)函數(shù)結(jié)果我們也知道了，n = 1會(huì)為遞歸結(jié)束的條件呢。大家可以想我們這個(gè)遞歸是要干什么的，不就是求n的階乘嗎，既然我們都知道到n=1的階乘為1了，那么到這里就要結(jié)束函數(shù)遞歸了。所以說，遞歸結(jié)束的條件：可以理解為我們所知道的函數(shù)結(jié)果的那個(gè)參數(shù)值，也就是n是一個(gè)很小的值。

步驟三：找出函數(shù)的等價(jià)條件

就是我們要不斷遵循把大事化小的思路，把參數(shù)范圍不斷縮小，我們可以通過一些輔助的變量或者操作，使得原函數(shù)的結(jié)果不變。

例如，demand_factorial（n）這個(gè)范圍比較大，我們可以變?yōu)閐emand_factorial（n）=n*

demand_factorial(n-1)，注意n的范圍就變成n-1了，為了讓原函數(shù)不變，我們需要讓demand_factorial(n-1)*n.其實(shí)，我們就是在為原函數(shù)尋找一個(gè)等價(jià)式。

這一步驟也是最難的大家可以細(xì)細(xì)體會(huì)，下面我們繼續(xù)完善代碼。

//求n的階乘
int demand_factorial(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return  demand_factorial(n - 1) * n;
	}
}

大家看完上面的思路可能還是不怎么理解，沒關(guān)系，我會(huì)帶這個(gè)思路繼續(xù)為大家分享幾道題目。

• 題目1 strlen的模擬（遞歸實(shí)現(xiàn)）

大家繼續(xù)按照上面的思路來求解這道題目

1 明確你函數(shù)要實(shí)現(xiàn)的功能。

假設(shè)my_strlen（str）是實(shí)現(xiàn)求字符串的長(zhǎng)度,代碼如下：

//用遞歸模擬strlen
//str為數(shù)組名
int my_strlen(char* str)
{
}

2 找出遞歸結(jié)束的條件

我們明白在一個(gè)字符串中他的結(jié)束標(biāo)志是'\0'，這時(shí)函數(shù)結(jié)果就是0，所以，很明顯遞歸結(jié)束的條件為*str='\0'.代碼如下

//用遞歸模擬strlen
//str為數(shù)組名
int my_strlen(char* str)
{
	if (*str == '\0')
	{
		return 0;
	}
}

3 找出函數(shù)的等價(jià)條件

為了求出字符串的長(zhǎng)度，我們肯定是從第一個(gè)字符開始數(shù)，只到數(shù)到我們遞歸結(jié)束條件為止。那么該函數(shù)的等價(jià)為：1+my_strlen(str+1）。其中的my_strlen(str+1)是為了尋找下個(gè)字符長(zhǎng)度。代碼完善如下：

/用遞歸模擬strlen
//str為數(shù)組名
int my_strlen(char* str)
{
	if (*str == '\0')
	{
		return 0;
	}
	else
	{
		return 1 + my_strlen(str + 1);
	}
}

這道題就ok了，大家是否有所體會(huì)呢？如果還是不理解我們繼續(xù)按照這個(gè)模式多加練習(xí)。

• 題目2斐波那契數(shù)列

斐波那契數(shù)列指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞推的方法定義：F (0)=0， F (1)=1, F (n)= F (n - 1)+ F (n - 2)，求第n項(xiàng)和。

1 明確你函數(shù)要實(shí)現(xiàn)的功能。

假設(shè)fib(n)是實(shí)現(xiàn)求第n個(gè)斐波那契數(shù)，代碼如下:

//求第n個(gè)斐波那契數(shù)
int fib(int n)
{
}

2 找出遞歸結(jié)束的條件

很明顯我們知道當(dāng)n=1或者n=2的時(shí)候斐波那契數(shù)都為1，所以，遞歸的結(jié)束條件為n<=2,那么函數(shù)的返回值便為1.代碼如下：

//求第n個(gè)斐波那契數(shù)
int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
}

3 找出函數(shù)的等價(jià)條件

對(duì)于函數(shù)的等價(jià)條件，題目已經(jīng)給我們了F (n)= F (n - 1)+ F (n - 2)，所以，代碼完善如下：

//求第n個(gè)斐波那契數(shù)
int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return fib(n - 1) + fib(n + 2);
	}
}

• 題目3 小青蛙跳臺(tái)階問題

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

1 明確你函數(shù)要實(shí)現(xiàn)的功能

假設(shè) (n) 的功能是求青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法，代碼如下：

//小青蛙跳臺(tái)階問題
int jump(int n)
{
}

2 找出遞歸結(jié)束的條件

上面說了，求遞歸結(jié)束的條件，你直接把 n 范圍變的很小就好，因?yàn)?n 越小，我們就越容易直觀著算出 f(n) 的多少，所以當(dāng) n = 1時(shí)，我們很容易知道f(1) = 1。代碼如下：

//小青蛙跳臺(tái)階問題
int jump(int n)
{
	if (n == 1)
	{
		return 1;
	}
}

3 找出函數(shù)的等價(jià)條件

我們知道青蛙每次跳臺(tái)階，可以跳一個(gè)臺(tái)階，也可以跳二個(gè)臺(tái)階，所以說青蛙每次跳臺(tái)階都有二種跳法。

第一種跳法，第一次跳1個(gè)臺(tái)階，那么還有n-1個(gè)臺(tái)階沒跳，剩下的n-1個(gè)臺(tái)階有jump(n-1)種跳法。

第二種跳法，第一次跳2個(gè)臺(tái)階，那么還有n-2個(gè)臺(tái)階沒跳，剩下的n-2個(gè)臺(tái)階有jump(n-2)種跳法。

所以青蛙所以跳法為：jump(n-1)+jump(n-2)，即等價(jià)關(guān)系式為：jump(n)=jump(n-1)+jump(n-2)代碼如下

//小青蛙跳臺(tái)階問題
int jump(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return jump(n - 1) + jump(n - 2);
	}
}

大家認(rèn)為上面的代碼對(duì)嗎?嘻嘻既然我這么問了，肯定是有問題的了，當(dāng)我們把代碼運(yùn)行起來的時(shí)候會(huì)發(fā)現(xiàn)，代碼死遞歸了，這個(gè)時(shí)候問題肯定就出現(xiàn)在遞歸條件上了，我們的遞歸條件是不嚴(yán)謹(jǐn)?shù)摹．?dāng)n=2時(shí)，顯然，jump(2)=jump(1)+jump(0),我們知道jump(0)=0，按道理遞歸該結(jié)束，但是我們上面代碼的邏輯中會(huì)繼續(xù)調(diào)用jump(0)=jump(-1)+jump(-2),這樣就會(huì)導(dǎo)致進(jìn)入死循環(huán)，無限調(diào)用。

為了防止出現(xiàn)遞歸結(jié)束條件出現(xiàn)不嚴(yán)謹(jǐn)?shù)默F(xiàn)象，我們每次進(jìn)行第三步后，應(yīng)該返回第二步，看根據(jù)函數(shù)的調(diào)用關(guān)系會(huì)不會(huì)出現(xiàn)一些漏掉的一些結(jié)束條件。當(dāng)我們把條件補(bǔ)全，代碼如下：

//小青蛙跳臺(tái)階問題
int jump(int n)
{
	if (n <= 2)
	{
		return n;
	}
	else
	{
		return jump(n - 1) + jump(n - 2);
	}
}

今天題目就和大家做到這里了，大家如果還覺的不過癮。我在后面為大家準(zhǔn)備了幾道題目大家可以去練習(xí)。下面我要繼續(xù)為大家分享有關(guān)遞歸于迭代的問題。

遞歸與迭代

我想對(duì)大家說是并不是所有復(fù)雜問題，都可以用遞歸來解決，就算可以也會(huì)出現(xiàn)許多問題。我們繼續(xù)回到斐波那契數(shù)列問題。

//求第n個(gè)斐波那契數(shù)
int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return fib(n - 1) + fib(n + 2);
	}
}

當(dāng)我們求的第n的比較大的時(shí)候，代碼會(huì)報(bào)錯(cuò)，stack overflow（棧溢出） 這樣的信息。

系統(tǒng)分配給程序的棧空間是有限的，但是如果出現(xiàn)了死循環(huán)，或者（死遞歸），這樣有可能導(dǎo)致一 直開辟棧空間，最終產(chǎn)生棧空間耗盡的情況，這樣的現(xiàn)象我們稱為棧溢出。

為什么說當(dāng)n很大的時(shí)候會(huì)，會(huì)出現(xiàn)報(bào)錯(cuò)呢？當(dāng)n=50時(shí)，我們來看下面這幅圖。

我們?yōu)榱饲骹(50)就要知道f(49)于f(48)以此類推，將會(huì)導(dǎo)致出現(xiàn)許多不必要的調(diào)用。

當(dāng)我們修改一下代碼

nt count = 0;//全局變量
int fib(int n)
{
 if(n == 3)
 count++;
 if (n <= 2)         
 return 1;
    else
    return fib(n - 1) + fib(n - 2);
}

會(huì)發(fā)現(xiàn)count是個(gè)很大的值，也就是說f(3)被重復(fù)調(diào)用了許多次。這樣我們就不難找出當(dāng)n是個(gè)很大的值的時(shí)候?yàn)槭裁磿?huì)報(bào)錯(cuò)了，很明顯這里將會(huì)棧溢出。

這里我們用迭代的方法寫一下將會(huì)解決棧溢出的問題。

//求第n個(gè)斐波那契數(shù)
int fib(int n)
{
	int result;
	int pre_result;
	int next_older_result;
	result = pre_result = 1;
	while (n > 2)
	{
		n -= 1;
		next_older_result = pre_result;
		pre_result = result;
		result = pre_result + next_older_result;
	}
	return result;
}

總結(jié)：

1我們?cè)谟眠f歸的時(shí)候是為了更好的解決問題，因?yàn)樗问礁忧逦?/p>

2當(dāng)發(fā)現(xiàn)遞歸會(huì)出現(xiàn)棧溢出的現(xiàn)象時(shí)不妨換用迭代的方式解決。

練習(xí)題

• 題目1打印一個(gè)數(shù)的每一位

類容：

遞歸方式實(shí)現(xiàn)打印一個(gè)整數(shù)的每一位

• 題目2字符串逆序（遞歸實(shí)現(xiàn)）

類容：

編寫一個(gè)函數(shù) reverse_string(char * string)（遞歸實(shí)現(xiàn)）

實(shí)現(xiàn)：將參數(shù)字符串中的字符反向排列，不是逆序打印。

要求：不能使用C函數(shù)庫(kù)中的字符串操作函數(shù)。

比如:

char arr[] = "abcdef";

逆序之后數(shù)組的內(nèi)容變成：fedcba

• 題目3遞歸實(shí)現(xiàn)n的k次方

內(nèi)容：

編寫一個(gè)函數(shù)實(shí)現(xiàn)n的k次方，使用遞歸實(shí)現(xiàn)。

• 題目4漢諾塔問題

內(nèi)容：

相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號(hào)A、B、C)，在A桿自下而上、由大到小按順序放置64個(gè)金盤(如圖1)。游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。操作規(guī)則：每次只能移動(dòng)一個(gè)盤子，并且在移動(dòng)過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。請(qǐng)用遞歸實(shí)現(xiàn)。

結(jié)束語(yǔ)

遞歸還是挺難的，大家還是要做幾到題目，不理解的地方還可以畫圖理解。