數(shù)據(jù)結(jié)構(gòu)主講人：閭楓常州信息職業(yè)技術(shù)學(xué)院3.3遞歸遞歸在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中是一種非常有效的問題求解方法，遞歸(recursion)是指在定義自身的同時(shí)又出現(xiàn)了對(duì)自身的直接或間接引用。引言IntroductionPart01遞歸的概念遞歸的基本思想是把規(guī)模大的復(fù)雜問題轉(zhuǎn)化為相似的規(guī)模小的子問題來解決。斐波那契數(shù)列的對(duì)于原問題F(n)的求解可以轉(zhuǎn)為對(duì)F(n-1)、F(n-2)兩個(gè)子問題的求解，F(xiàn)(n-1)的求解又可分解為F(n-2)、F(n-3)兩個(gè)子問題的求解，依次遞推下去，一直到F(2)、F(1)的求解，而F(2)、F(1)數(shù)值是確定的，因此F(n)值得解。遞歸思想說明遞歸的概念

斐波那契(Fibonacci)數(shù)列{1、1、2、3、5、8、13、21、34、……}遞歸的求解遞歸的概念先將原問題分解為規(guī)模較小的子問題，分解后的子問題與原問題類型相同，求解方法一樣再將子問題繼續(xù)分解，反復(fù)進(jìn)行到不能再劃分或已經(jīng)可以求解為止最小子問題解決，則它的上一層子問題得解，依次回溯最后獲得原問題的解F(n)F(n-2)F(n-2)F(n-3)F(n-1)F(n-3)F(n-4)……F(n-3)F(n-4)……F(1)F(2)F(1)F(2)遞歸的求解遞歸的概念遞歸求解過程包括兩個(gè)必要條件：遞推和回歸。5!5*4!

4*3!

3*2!

2*1!

1*0!

遞推回歸=1=2=6=24=120

遞歸邊界：0!=1遞推過程分析得到的規(guī)律即遞推公式，回歸點(diǎn)即遞歸邊界，是遞歸終止條件，到達(dá)后則回歸。n！=n*(n-1)!(n>=1)=120

Part02遞歸算法遞歸函數(shù)必須有遞歸邊界，函數(shù)的無(wú)限遞歸會(huì)導(dǎo)致程序崩潰。遞歸算法和遞歸函數(shù)遞歸算法遞歸算法是遞歸思維在程序中的體現(xiàn)，遞歸函數(shù)是指在函數(shù)的定義中直接或間接調(diào)用自身的函數(shù)。遞歸函數(shù)執(zhí)行時(shí)會(huì)反復(fù)判斷邊界條件，條件不滿足時(shí)，遞歸前進(jìn)，當(dāng)邊界條件滿足時(shí)，遞歸返回。遞歸算法和遞歸函數(shù)遞歸算法（1）問題能否分解成多個(gè)同類子問題，并且解決方法相同；（2）問題的分解是否有終止條件。寫遞歸關(guān)鍵的兩點(diǎn)就是找出遞推公式和明確遞歸邊界sum(n)=1+2+3+……+(n-1)+nsum(n-1)sum(n-1)=1+2+3+……+(n-2)+(n-1)sum(n-2)推導(dǎo)得到遞推公式為：sum(n)=sum(n-1)+n遞歸邊界為：n=1時(shí)，sum(1)值為1//遞歸求和的方法public

static

intsum(int

n){

if(n==1)return1;//遞歸邊界

else

return

n+sum(n-1);//遞推公式}遞歸求解Fibonacci遞歸算法（1）斐波那契數(shù)列的遞推公式為：F(n)=F(n-1)+F(n-2)(n>2)（2）遞歸邊界為:F(1)=F(2)=1(n=1,2)//遞歸求解Fibonacci數(shù)列的第n項(xiàng)public

static

intfib(int

n){

if(n<=0)

throw

newRuntimeException("無(wú)效參數(shù)");

if(n==1||n==2)return1;//遞歸邊界，n為1或2,函數(shù)值為1，直接返回

return

fib(n-1)+fib(n-2);//遞推公式，n不是邊界值，遞歸調(diào)用}fib(6)fib(5)fib(4)fib(3)fib(3)fib(2)fib(2)fib(1)fib(2)fib(1)fib(4)fib(3)fib(2)fib(2)fib(1)111211111223538遞歸求解Fibonacci遞歸算法數(shù)列求解過程中，存在重復(fù)遞歸計(jì)算問題，若計(jì)算第n項(xiàng)，n值越大，重復(fù)計(jì)算越多。重復(fù)計(jì)算會(huì)導(dǎo)致程序的時(shí)間復(fù)雜度提高，導(dǎo)致程序效率低下。將計(jì)算過的數(shù)值先保存到集合容器中，每次遞歸計(jì)算前檢查容器中是否有該數(shù)據(jù)，若有，則直接拿來使用，若沒有，則計(jì)算并保存到容器中。//改進(jìn)的Fibonacci數(shù)列的第n項(xiàng)，避免重復(fù)計(jì)算public

static

intfib(int

n){

if(n<=0)

throw

newRuntimeException("無(wú)效參數(shù)");

if(n==1||n==2)return1;//遞歸邊界，n為1或2,函數(shù)值為1，直接返回

//用一個(gè)map存放已經(jīng)計(jì)算出來的數(shù)值，判斷fib(n)是否已經(jīng)計(jì)算過，若是，則直接從map中取值返回

if(map.containsKey(n)){

return

map.get(n); }

//若fib(n)沒有計(jì)算過，map中沒有包含其值，則用遞推公式進(jìn)行計(jì)算

int

num=fib(n-1)+fib(n-2);

//計(jì)算得到的fib(n)數(shù)據(jù)存放到map中

map.put(n,num);

return

num;}遞歸算法函數(shù)調(diào)用執(zhí)行是不斷壓棧和出棧過程，遞歸函數(shù)調(diào)用時(shí)在函數(shù)里調(diào)用自身，且當(dāng)前函數(shù)并未結(jié)束，層層遞歸進(jìn)去，直到遞歸邊界。系統(tǒng)棧的大小是有限的，遞歸深度太深，不斷壓棧可能會(huì)導(dǎo)致棧滿溢出，以致程序崩潰。階乘算法中，為避免棧溢出可以設(shè)置一個(gè)遞歸深度值，若超過預(yù)設(shè)的遞歸深度值，則結(jié)束程序，不再遞歸下去。假如有n個(gè)臺(tái)階，每次可以跨一個(gè)或者兩個(gè)臺(tái)階，若要找出走n個(gè)臺(tái)階有多少種走法，請(qǐng)用遞歸求解，分析找出遞推公式和遞歸邊界。思考CerebratePart03遞歸算法應(yīng)用遞歸算法的關(guān)鍵就是找到如何將大問題分解為小問題的規(guī)律，基于規(guī)律寫出遞推公式，然后再推敲遞歸邊界，最后將遞推公式和遞歸邊界翻譯成代碼。遞歸算法應(yīng)用單鏈表的遞歸創(chuàng)建算法實(shí)現(xiàn)：函數(shù)的參數(shù)為結(jié)點(diǎn)個(gè)數(shù)，同時(shí)用于設(shè)置結(jié)點(diǎn)的數(shù)據(jù)域的值，返回值為頭結(jié)點(diǎn)。//遞歸創(chuàng)建鏈表，n表示結(jié)點(diǎn)個(gè)數(shù)publicLinkedNode<T>create(int

n){

if(n<=0){

return

null; }

//構(gòu)造一個(gè)新結(jié)點(diǎn) LinkedNode<T>node=newLinkedNode(n,null);

//node的next指向下一個(gè)結(jié)點(diǎn)，下一個(gè)結(jié)點(diǎn)用遞歸構(gòu)造

node.setNext(create(n-1));

return

node;}遞歸算法應(yīng)用單鏈表的遞歸創(chuàng)建以遞歸思想來看單鏈表，每個(gè)結(jié)點(diǎn)的next指向以其后繼結(jié)點(diǎn)開始的一個(gè)子鏈表，最后一個(gè)結(jié)點(diǎn)的next指向NULL算法分析：?jiǎn)捂湵淼慕Y(jié)點(diǎn)數(shù)量由用戶指定，假設(shè)有n個(gè)結(jié)點(diǎn)的單鏈表。創(chuàng)建一個(gè)結(jié)點(diǎn)作為頭結(jié)點(diǎn)并設(shè)置數(shù)據(jù)，其后的n-1個(gè)結(jié)點(diǎn)是子鏈表，第一個(gè)結(jié)點(diǎn)的next指向子鏈表的頭結(jié)點(diǎn)，返回第一個(gè)結(jié)點(diǎn)的地址。nhead頭結(jié)點(diǎn)包含n-1個(gè)結(jié)點(diǎn)的子鏈表對(duì)子鏈表使用遞歸方式繼續(xù)創(chuàng)建。遞歸邊界為n=0，即空鏈表的情況，若n為非法值，也設(shè)為空鏈表。。nhead包含n-2個(gè)結(jié)點(diǎn)的子鏈表n-1nheadn-11……NULL遞歸算法應(yīng)用單鏈表的遍歷算法分析：先獲取頭結(jié)點(diǎn)的數(shù)據(jù)域，存放到字符串中，其后剩下的結(jié)點(diǎn)作為一個(gè)子鏈表，再遞歸遍歷即可。遞歸結(jié)束條件是遍歷完最后一個(gè)結(jié)點(diǎn)后，鏈表為空的情況。//遞歸輸出單鏈表的結(jié)點(diǎn)publicStringprintNode(LinkedNode<T>p){

//遞歸邊界，若是空鏈表，輸出空串

if(p==null)return

"";

//取結(jié)點(diǎn)的數(shù)據(jù)域 Stringstr=p.getData().toString();

//若不是尾結(jié)點(diǎn)，則在結(jié)點(diǎn)數(shù)據(jù)后加上連接符

if(p.getNext()!=null){

str+="->"; }

//遞歸獲取結(jié)點(diǎn)的數(shù)據(jù)域

return

str+printNode(p.getNext());}

算法實(shí)現(xiàn)：將鏈表的頭結(jié)點(diǎn)作為參數(shù)，返回值為鏈表中結(jié)點(diǎn)數(shù)據(jù)域以一定格式連接后的字符串。遞歸算法應(yīng)用單鏈表的逆置算法分析：將包含n個(gè)元素的鏈表，看成是頭結(jié)點(diǎn)和包含n-1個(gè)結(jié)點(diǎn)的子鏈表，再將n-1個(gè)結(jié)點(diǎn)的子鏈表遞歸逆置。5node4321^將node之后的子鏈表逆置，headNode指向頭結(jié)點(diǎn)設(shè)置數(shù)值為4的結(jié)點(diǎn)next指向node，并設(shè)置node的next為NULL51234headNodenode^遞歸算法應(yīng)用單鏈表的逆置算法實(shí)現(xiàn)：定義方法reverseList，參數(shù)是鏈表的頭結(jié)點(diǎn)，返回值為逆置后鏈表的頭結(jié)點(diǎn)。//遞歸反轉(zhuǎn)單鏈表，返回新的頭結(jié)點(diǎn)publicLinkedNode<T>reverseList(LinkedNode<T>node){

//若是空鏈表或鏈表只有一個(gè)結(jié)點(diǎn)，直接返回空或頭結(jié)點(diǎn)

if(node==null||node.getNext()==null){

return

node; } LinkedNode<T>headNode=reverseList(node.getNext());

node.getNext().setNext(node);

node.setNext(null);//反轉(zhuǎn)后node為鏈表尾，其next指向?yàn)榭?/p>

return

headNode;//返回以headNode頭結(jié)點(diǎn)}//單鏈表的遞歸應(yīng)用測(cè)試public

classTestSinglyLinkedListByRecursion{public

static

voidmain(String[]args){

//創(chuàng)建單鏈表 SinglyLinkedList<Integer>slist=newSinglyLinkedList<Integer>();

slist.setHead(slist.create(10));

//遍歷輸出 System.out.println("初始鏈表\n"+slist.printNode(slist.getHead())); //逆置單鏈表,返回頭結(jié)點(diǎn) LinkedNode<Integer>reListHead=slist.reverseList(slist.getHead());

//遍歷輸出逆置后的單鏈表 System.out.println("逆置后的鏈表\n"+slist.printNode(reListHead));}}遞歸算法應(yīng)用漢諾塔問題問題描述：漢諾塔問題是由很多放置在三個(gè)塔座上的盤子組成的一個(gè)古老的難題。所有的盤子的直徑是不同，并且盤子中央都有一個(gè)洞使得它們剛好可以放在塔座上，初始從小到大放置在A塔座上，目標(biāo)是將所有的盤子借助塔座B從塔座A移動(dòng)到塔座C上，規(guī)定：每次只可以移動(dòng)一個(gè)盤子，并且任何一個(gè)盤子都不可以放置在比自己小的盤子之上。算法分析：假設(shè)給盤子編號(hào)：1、2、……、n，編號(hào)1是最小的，編號(hào)n是最大的。如果只有兩個(gè)盤子在A塔座上，上面就是盤子1，下面是盤子2，那么移動(dòng)步驟為：(1)將盤子1先移動(dòng)到B塔座上(2)將盤子2移動(dòng)到C塔座(3)將盤子1移動(dòng)到C塔座上ABC121：A->B2：A->C1：B->C遞歸算法應(yīng)用漢諾塔問題算法分析：若有三個(gè)盤子，那么移動(dòng)步驟為：(1)將盤子1放到C塔座(2)將盤子2放到B塔座(3)將C塔座的盤子1放到B塔座上(4)將A塔座的盤子3放到C塔座上(5)將B塔座的盤子1放到A塔座(6)將B塔座的盤子2放到C塔座(7)將A塔座的盤子1放到C塔座上ABC123遞歸算法應(yīng)用漢諾塔問題算法分析：無(wú)論有多少個(gè)盤子，我們都將其看做只有兩個(gè)盤子。假設(shè)有n個(gè)盤子在塔座A上，我們將其看為兩個(gè)盤子，其中上面的1~n-1個(gè)盤子看成是一個(gè)整體，最下面第n個(gè)盤子看成是一個(gè)盤子，遞歸算法為：（1）從初始塔座A上移動(dòng)包含n-1個(gè)盤子到輔助塔座B上。（2）將初始塔座A上剩余的一個(gè)盤子（最大的一個(gè)盤子）放到目標(biāo)塔座C上。（3）將輔助塔座B上n-1個(gè)盤子移動(dòng)到目標(biāo)塔座C上。ABCn12n-1……遞歸算法應(yīng)用漢諾塔問題算法實(shí)現(xiàn)：定義move方法，第一個(gè)參數(shù)代表盤子個(gè)數(shù)，后面三個(gè)參數(shù)代表三個(gè)塔座，A為源塔座，B為輔助塔座，C