遞歸的思想

以此類推是遞歸的基本思想。

具體來(lái)講就是把規(guī)模大的問(wèn)題轉(zhuǎn)化為規(guī)模小的相似的子問(wèn)題來(lái)解決。在函數(shù)實(shí)現(xiàn)時(shí)，因?yàn)榻鉀Q大問(wèn)題的方法和解決小問(wèn)題的方法往往是同一個(gè)方法，所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況。另外這個(gè)解決問(wèn)題的函數(shù)必須有明顯的結(jié)束條件，這樣就不會(huì)產(chǎn)生無(wú)限遞歸的情況了。

遞歸的兩個(gè)條件

可以通過(guò)遞歸調(diào)用來(lái)縮小問(wèn)題規(guī)模，且新問(wèn)題與原問(wèn)題有著相同的形式。(自身調(diào)用)

存在一種簡(jiǎn)單情境，可以使遞歸在簡(jiǎn)單情境下退出。(遞歸出口)

遞歸三要素：

一定有一種可以退出程序的情況;

總是在嘗試將一個(gè)問(wèn)題化簡(jiǎn)到更小的規(guī)模

父問(wèn)題與子問(wèn)題不能有重疊的部分

遞歸：自已(方法)調(diào)用自已

例子：用遞歸把目錄下所有的目錄及文件全部顯示出來(lái)

遞歸算法的一般形式：

例子

求一個(gè)數(shù)的階乘是練習(xí)簡(jiǎn)單而典型的例子，階乘的遞推公式為：factorial(n)=n*factorial(n-1)，其中n為非負(fù)整數(shù),且0!=1,1!=1

我們根據(jù)遞推公式可以輕松的寫(xiě)出其遞歸函數(shù)：

遞歸的過(guò)程

在求解6的階乘時(shí)，遞歸過(guò)程如下所示。

我們會(huì)驚奇的發(fā)現(xiàn)這個(gè)過(guò)程和棧的工作原理一致對(duì)，遞歸調(diào)用就是通過(guò)棧這種數(shù)據(jù)結(jié)構(gòu)完成的。整個(gè)過(guò)程實(shí)際上就是一個(gè)棧的入棧和出棧問(wèn)題。然而我們并不需要關(guān)心這個(gè)棧的實(shí)現(xiàn)，這個(gè)過(guò)程是由系統(tǒng)來(lái)完成的。

那么遞歸中的“遞”就是入棧，遞進(jìn);“歸”就是出棧，回歸。

我們可以通過(guò)一個(gè)更簡(jiǎn)單的程序來(lái)模擬遞進(jìn)和回歸的過(guò)程：

遞歸的例子

斐波那契數(shù)列

斐波那契數(shù)列的遞推公式:Fib(n)=Fib(n-1)+Fib(n-2)，指的是如下所示的數(shù)列：

1、1、2、3、5、8、13、21.....

按照其遞推公式寫(xiě)出的遞歸函數(shù)如下：

遞歸調(diào)用的過(guò)程像樹(shù)一樣，通過(guò)觀察會(huì)發(fā)現(xiàn)有很多重復(fù)的調(diào)用。

歸并排序

歸并排序也是遞歸的典型應(yīng)用，其思想：將序列分為若干有序序列（開(kāi)始為單個(gè)記錄），兩個(gè)相鄰有序的序列合并成一個(gè)有序的序列，以此類推，直到整個(gè)序列有序。

同樣調(diào)用過(guò)程向樹(shù)一樣，但是它并沒(méi)有重復(fù)調(diào)用的問(wèn)題。在遞進(jìn)的過(guò)程中拆分?jǐn)?shù)組，在回歸的過(guò)程合并數(shù)組。通過(guò)遞歸來(lái)實(shí)現(xiàn)歸并排序，程序結(jié)構(gòu)和條理非常清晰。

以上就是動(dòng)力節(jié)點(diǎn)java培訓(xùn)機(jī)構(gòu)的小編針對(duì)“編程入門(mén)技術(shù)分享：java遞歸學(xué)習(xí)”的內(nèi)容進(jìn)行的回答，希望對(duì)大家有所幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。