漫談遞歸思想

編程里面估計(jì)最讓人摸不著頭腦的基本算法就是遞歸了。很多時(shí)候我們看明白一個(gè)復(fù)雜的遞歸都有點(diǎn)費(fèi)時(shí)間，尤其對模型所描述的問題概念不清的時(shí)候，想要自己設(shè)計(jì)一個(gè)遞歸那么就更是有難度了。今天我也花費(fèi)了半個(gè)小時(shí)來搞明白二叉樹的平衡性的遞歸模型，首先我不明白什么叫做平衡性，所以花費(fèi)的時(shí)候大部分實(shí)在試探理解平衡性的含義。在搞明白的時(shí)候，我突然想到假如讓我來設(shè)計(jì)，在我知道平衡性的前提下，我是否可以建立如此簡潔的遞歸模型。為此，我遇到的問題是我們到底在什么情況下適用遞歸模型，并且遞歸模型如何建立。

數(shù)學(xué)都不差的我們，第一反應(yīng)就是遞歸在數(shù)學(xué)上的模型是什么。畢竟我們對于問題進(jìn)行數(shù)學(xué)建模比起代碼建模拿手多了。 （當(dāng)然如果對于問題很清楚的人也可以直接簡歷遞歸模型了，運(yùn)用數(shù)模做中介的是針對對于那些問題還不是很清楚的人）

自己觀察遞歸，我們會發(fā)現(xiàn)，遞歸的數(shù)學(xué)模型其實(shí)就是歸納法，這個(gè)在高中的數(shù)列里面是最常用的了。回憶一下歸納法。

歸納法適用于想解決一個(gè)問題轉(zhuǎn)化為解決他的子問題，而他的子問題又變成子問題的子問題，而且我們發(fā)現(xiàn)這些問題其實(shí)都是一個(gè)模型，也就是說存在相同的邏輯歸納處理項(xiàng)。當(dāng)然有一個(gè)是例外的，也就是遞歸結(jié)束的哪一個(gè)處理方法不適用于我們的歸納處理項(xiàng)，當(dāng)然也不能適用，否則我們就無窮遞歸了。這里又引出了一個(gè)歸納終結(jié)點(diǎn)以及直接求解的表達(dá)式。如果運(yùn)用列表來形容歸納法就是：

步進(jìn)表達(dá)式：問題蛻變成子問題的表達(dá)式

結(jié)束條件：什么時(shí)候可以不再是用步進(jìn)表達(dá)式

直接求解表達(dá)式：在結(jié)束條件下能夠直接計(jì)算返回值的表達(dá)式

邏輯歸納項(xiàng)：適用于一切非適用于結(jié)束條件的子問題的處理，當(dāng)然上面的步進(jìn)表達(dá)式其實(shí)就是包含在這里面了。

這樣其實(shí)就結(jié)束了，遞歸也就出來了。

遞歸算法的一般形式：???
? ? void ? func( mode){ ??
? ? ? ? ? if(endCondition){ ??
? ? ? ? ? ? ? ? ?constExpression?? ? ??//基本項(xiàng)??
? ? ? ? ? } ??
? ? ? ? ? else

{

accumrateExpreesion /歸納項(xiàng)

mode=expression?//步進(jìn)表達(dá)式

func(mode) /?/調(diào)用本身，遞歸

}?

}

最典型的就是N！算法，這個(gè)最具有說服力。理解了遞歸的思想以及使用場景，基本就能自己設(shè)計(jì)了，當(dāng)然要想和其他算法結(jié)合起來使用，還需要不斷實(shí)踐與總結(jié)了。

例如：返回一個(gè)二叉樹的深度：

int depth(Tree t){?
if(!t) return 0;?
else {?
?????????int a=depth(t.right);?
?????????int b=depth(t.left);?
?????????return (a>b)?(a+1):(b+1);?
????}?
}

判斷一個(gè)二叉樹是否平衡：

int isB(Tree t){?
????if(!t) return 0;?
????int left=isB(t.left);?
????int right=isB(t.right);?
????if( left >=0 && right >=0 && left - right <= 1 || left -right >=-1)?
?????????return (left<right)? (right +1) : (left + 1);?
????else return -1;?
}

?

上面這兩個(gè)遞歸的難易程度就不一樣了，第一個(gè)關(guān)于深度的遞歸估計(jì)只要了解遞歸思想的都可以短時(shí)間設(shè)計(jì)出來，但第二個(gè)估計(jì)就要長點(diǎn)時(shí)間了。純遞歸問題的難易主要糾結(jié)于一些條件表達(dá)式的構(gòu)造以及初值的設(shè)置（上面的為直接表達(dá)式值的設(shè)定）。

?

最后需要補(bǔ)充的是，很多不理解遞歸的人（今天在csdn里面看到一個(gè)初學(xué)者的留言），總認(rèn)為遞歸完全沒必要，用循環(huán)就可以實(shí)現(xiàn)，其實(shí)這是一種很膚淺的理解。因?yàn)檫f歸之所以在程序中能風(fēng)靡并不是因?yàn)樗难h(huán)，大家都知道遞歸分兩步，遞和歸，那么可以知道遞歸對于空間性能來說，簡直就是造孽，這對于追求時(shí)空完美的人來說，簡直無法接接受，如果遞歸僅僅是循環(huán)，估計(jì)現(xiàn)在我們就看不到遞歸了。遞歸之所以現(xiàn)在還存在是因?yàn)檫f歸可以產(chǎn)生無限循環(huán)體，也就是說有可能產(chǎn)生100層也可能10000層for循環(huán)。例如對于一個(gè)字符串進(jìn)行全排列，字符串長度不定，那么如果你用循環(huán)來實(shí)現(xiàn)，你會發(fā)現(xiàn)你根本寫不出來，這個(gè)時(shí)候就要調(diào)用遞歸，而且在遞歸模型里面還可以使用分支遞歸，例如for循環(huán)與遞歸嵌套，或者這節(jié)枚舉幾個(gè)遞歸步進(jìn)表達(dá)式，每一個(gè)形成一個(gè)遞歸。

轉(zhuǎn)載于:https://www.cnblogs.com/Roni-i/p/7243016.html

總結(jié)

以上是生活随笔為你收集整理的漫谈递归思想（转）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。