遞歸

我們先說遞歸，在定義上來講：我們把一個(gè)直接調(diào)用自己或者通過一系列的調(diào)用語句間接調(diào)用自己的函數(shù)，稱為遞歸函數(shù)。

我們應(yīng)該還記得一個(gè)非常有名的數(shù)列：斐波那契額數(shù)列。在這里一起回憶下：假如兔子在出生兩個(gè)月后就具有繁殖能力，而且一對(duì)兔子每個(gè)月能生出一對(duì)小兔子，并且假設(shè)所有兔子都不會(huì)死，那么一年以后總共有多少兔子呢？十年呢？

在這里，很容易發(fā)現(xiàn)的一個(gè)規(guī)律是：前兩項(xiàng)之和等于后一項(xiàng)

其數(shù)學(xué)表達(dá)式為：

其代碼實(shí)現(xiàn)非常的簡潔：（我就不寫注釋了）

談?wù)勛约簩?duì)遞歸的理解：

首先，如果某個(gè)問題你考慮用遞歸來解決，應(yīng)該如何判斷其是否適合？

- 這個(gè)問題是否能拆解為許多邏輯完全一致的小問題？

- 這個(gè)問題是否具有終止條件？

如果這兩個(gè)條件都滿足了，這個(gè)問題應(yīng)該是可以用遞歸解決的，但是，遞歸又容易出現(xiàn)其他的問題，比如：

堆棧溢出，重復(fù)計(jì)算等等（不多說，坑大家一起踩，嘻嘻）

堆棧溢出的一種解決方案時(shí)限定遞歸條件，比如說限定其遞歸到哪一層就結(jié)束并返回。但是這種方案時(shí)有局限性的，只適合預(yù)估最大遞歸深度層數(shù)較少的時(shí)候。

重復(fù)計(jì)算是指在遞歸的過程中，同一個(gè)遞歸函數(shù)被計(jì)算了多次：比如在斐波那契額數(shù)列中，F(xiàn)(4)的計(jì)算需要用到F(3)，F(xiàn)(5)的計(jì)算也需要用到F(3)，如果遞歸層數(shù)足夠多，是非常消耗資源的。

對(duì)于重復(fù)計(jì)算，一種解決方案是：將計(jì)算過的F(n)保存在一個(gè)散列表中，在遞歸過程中，檢查F(k)是否被計(jì)算過，如果是，則直接從散列表中返回。

四則運(yùn)算表達(dá)式求值

我們要計(jì)算：6 + （4 - 1）* 2 - 8 / 2很簡單，口算就可以很快算出來（其中的“/”為除以），但是，計(jì)算機(jī)時(shí)怎么算的你知道嗎？這時(shí)候，棧這種數(shù)據(jù)結(jié)構(gòu)又派上用場(chǎng)了！

在了解計(jì)算機(jī)如何計(jì)算之前，我們先來緬懷一下想出一種不需要括號(hào)的后綴表達(dá)法而又沒有以他的名字命名的波蘭邏輯學(xué)家：Jan Lukasiewicz（可能是由于名字太復(fù)雜了），這種表示法被后人稱為：逆波蘭表示

如果以上式子用后綴表達(dá)法應(yīng)該表示成什么形式呢？

6 4 1 - 2 * + 8 2 / -? ? ，我們稱這種式子為后綴表達(dá)式

我們先來看看計(jì)算機(jī)是如何通過這個(gè)后綴表達(dá)式來計(jì)算的：

1. 初始化一個(gè)空棧，用以存儲(chǔ)表達(dá)式上的數(shù)字和符號(hào)；

2. 表達(dá)式的6 4 1都是數(shù)字，依次進(jìn)棧；

3. 下一個(gè)為符號(hào)“-”，便兩次取出棧頂元素，使得1為減數(shù)，4為被減數(shù)，計(jì)算后結(jié)果為3，并將3入棧；

4. 然后是數(shù)字2，進(jìn)棧；

5. 接著是符號(hào) * ，則兩次取出棧頂元素，將3 和 2做乘法運(yùn)算，得到 6，將6進(jìn)棧；

6. 接下來是符號(hào)“ + ”，則兩次取出棧頂元素，將6 和 6做加法預(yù)算，得到12，并將12進(jìn)棧；

7. 下一個(gè)是數(shù)字8 和 2，依次進(jìn)棧；

8. 接著是符號(hào)“/”，則兩次取出棧頂元素，將2視為除數(shù)，將8視為被除數(shù)，計(jì)算結(jié)果為4，將4進(jìn)棧；

9. 最后是符號(hào)“-”，兩次取出棧頂元素，計(jì)算12 - 4，結(jié)果為8；

10. 結(jié)果8出棧，棧變?yōu)榭眨?/p>

示意圖如下：（靈魂畫手）

理解了計(jì)算及如果通過棧求四則運(yùn)算表達(dá)式的值，我們來談?wù)勥@個(gè)逆波蘭表示

我們先約定（其實(shí)本來就這樣叫），6 + （4 - 1）* 2 - 8 / 2這種給人看的叫：中綴表達(dá)式；

而6 4 1 - 2 * + 8 2 / - 這種給計(jì)算機(jī)看的叫：后綴表達(dá)式

轉(zhuǎn)化規(guī)則為：

從左到右遍歷中綴表達(dá)式的數(shù)字和符號(hào)，若是數(shù)字則輸出，即稱為后綴表達(dá)式的一部分；若是符號(hào)，則判斷其與棧頂符號(hào)的優(yōu)先級(jí)，是右括號(hào)或優(yōu)先級(jí)不高于棧頂符號(hào)，則棧頂元素依次出棧并輸出，并將當(dāng)前符號(hào)進(jìn)棧，一致到最終輸出后綴表達(dá)式為止。

是不是看完之后有種：“你盡管講，看得懂算我輸！”的感覺？沒關(guān)系，我們一步步來說，就拿上一個(gè)例子：

1. 初始化一個(gè)空棧，用來存儲(chǔ)數(shù)字和符號(hào)；

2. 第一個(gè)數(shù)字是6，直接輸出；此時(shí)輸出為：6

3. 后一個(gè)是符號(hào)“+”和符號(hào)“（”，直接依次進(jìn)棧；

4. 接著是數(shù)字 4 ，直接輸出；此時(shí)輸出為：6 4

5. 下一個(gè)是減號(hào)“-”，進(jìn)棧，因?yàn)椤?”的優(yōu)先級(jí)比“（”低；后面是數(shù)字“1”，直接輸出；此時(shí)輸出為： 6 4 1

6. 后一個(gè)是右括號(hào)“）”，有右括號(hào)則輸出棧頂元素“-”，直到左括號(hào)“（”出棧為止（注意：括號(hào)并不輸出）；此時(shí)輸出為 6 4 1 -

7. 接下來是乘號(hào)“*”，進(jìn)棧，因?yàn)閮?yōu)先級(jí)高于棧頂符號(hào)“+”；緊接著是數(shù)字2，直接輸出；此時(shí)輸出為：6 4 1 - 2

8. 接著是符號(hào)“-”，其優(yōu)先級(jí)低于棧頂符號(hào)“*”，則將棧頂符號(hào)出棧，將“-”與棧頂元素比較；并且此時(shí)符號(hào)“-”的優(yōu)先級(jí)并不比棧頂元素“+”高，則將“+”輸出，將“-”入棧；此時(shí)輸出為： 6 4 1 - 2 * +

9. 接著是數(shù)字8，直接輸出；后面是符號(hào)“/”，直接進(jìn)棧；此時(shí)輸出為：6 4 1 - 2 * + 8

10. 接著是數(shù)字2，直接輸出；此時(shí)輸出為：6 4 1 - 2 * + 8 2

11. 將棧中元素依次輸出；此時(shí)輸出為：6 4 1 - 2 * + 8 2 / -

繞暈了？

靈魂畫手又來了：