日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
寫給小白看的遞歸(硬核)

大家好，我是bigsai，之前有老弟說弄不懂遞歸，今天給大家講講遞歸。

創(chuàng)新互聯(lián)公司是專業(yè)的費(fèi)縣網(wǎng)站建設(shè)公司，費(fèi)縣接單;提供成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì),網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行費(fèi)縣網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

什么是遞歸?

遞歸：就是函數(shù)自己調(diào)用自己。子問題須與原始問題為同樣的事，或者更為簡(jiǎn)單。

遞歸通常可以簡(jiǎn)單的處理子問題，但是不一定是最好的解決方式。

對(duì)于遞歸要分清以下概念：

  • 遞歸是自己調(diào)用自己
  • 遞歸通常不在意具體操作，只關(guān)心初始條件、結(jié)束條件和上下層的變化關(guān)系。
  • 遞歸函數(shù)需要有臨界停止點(diǎn)(結(jié)束條件)，即遞歸不能無限制的執(zhí)行下去。通常這個(gè)點(diǎn)為必須經(jīng)過的一個(gè)數(shù)。
  • 遞歸可以被棧替代。有些遞歸可以優(yōu)化。比如遇到重復(fù)性的可以借助空間內(nèi)存記錄而減少遞歸的次數(shù)

認(rèn)識(shí)遞歸，遞歸函數(shù)通?？雌饋砗?jiǎn)易但是對(duì)于初學(xué)者可能很難去理解它，拿一個(gè)遞歸函數(shù)來說。

 
 
 
 
      
  
  
  
  1. static void digui() 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     System.out.println("bigsai前"); 
    4.   
  
  
  
  4.     digui(); 
    5.   
  
  
  
  5.     System.out.println("bigsai后"); 
    6.   
  
  
  
  6. } 
    7.

這是一個(gè)遞歸嘛?不是正常遞歸，沒有結(jié)束條件，自己一致調(diào)用自己導(dǎo)致無限循環(huán)。

那正確的遞歸應(yīng)該這樣

 
 
 
 
      
  
  
  
  1. static void digui(int time) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if(time==0) {}//time==0不執(zhí)行 
    4.   
  
  
  
  4.     else { 
    5.   
  
  
  
  5.         System.out.println("bigsai前time: "+time); 
    6.   
  
  
  
  6.         digui(time-1); 
    7.   
  
  
  
  7.         System.out.println("bigsai后time: "+time);    
    8.   
  
  
  
  8.     }    
    9.   
  
  
  
  9. } 
    10.

對(duì)于這樣一種遞歸，它的流程大致是這樣的

 
 
 
 
      
  
  
  
  1. 定義遞歸算法及參數(shù) 
    2.   
  
  
  
  2. - 停止遞歸算法條件 
    3.   
  
  
  
  3. - (可存在)其他邏輯 
    4.   
  
  
  
  4. - 遞歸調(diào)用(參數(shù)需要改變) 
    5.   
  
  
  
  5. - (可存在)其他邏輯 
    6.

所以，調(diào)用digui(5)在控制臺(tái)輸出是這樣的

那么，我想你對(duì)遞歸函數(shù)執(zhí)行的流程應(yīng)該有所了解了吧。

遞歸求階乘

初學(xué)遞歸，接觸最多的就是遞歸求階乘，為啥階乘可以用遞歸來求呢? 我們首先看下階乘，n的階乘表示為：

n!=n*(n-1)*……*1

n的階乘就是從1開始疊乘到n，那么n-1的階乘為：

(n-1)!=(n-1)*(n-2)*……*1

通過觀察就能知道n的階乘和n-1的階乘有這樣的關(guān)系：

n!=n!=n*(n-1)!

所以，我們要求n的階乘，我們知道n-1的階乘乘以n就可以得到，這就是最核心的關(guān)系。

0的階乘為1，通過階乘上下級(jí)的關(guān)系，我們假設(shè)一個(gè)函數(shù)jiecheng(n)為求n的階乘的函數(shù)，那么這個(gè)函數(shù)為：

 
 
 
 
      
  
  
  
  1. static int jiecheng(int n) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if(n==0)//0的階乘為1 
    4.   
  
  
  
  4.     { 
    5.   
  
  
  
  5.         return 1; 
    6.   
  
  
  
  6.     } 
    7.   
  
  
  
  7.     else { 
    8.   
  
  
  
  8.         return n*jiecheng(n-1);//return n*(n-1)*jiecheng(n-2)=------- 
    9.   
  
  
  
  9.     } 
    10.   
  
  
  
  10. } 
    11.

運(yùn)行流程為這樣：

遞歸求斐波那契

斐波那契數(shù)列，已經(jīng)跟隨我們成長(zhǎng)很久很久了，除了直接的斐波那契，爬樓梯等問題也和斐波那契問題差不多。

首先，求斐波那契的公式為：

F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)

也就是除了n=1和2特殊以外，其他均是可以使用遞推式，按照上述遞歸思想，我們假設(shè)求斐波那契設(shè)成F(n);

那么遞推實(shí)現(xiàn)的代碼為：

 
 
 
 
      
  
  
  
  1. static long F(int n) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if(n==1||n==2) {return 1;} 
    4.   
  
  
  
  4.     else { 
    5.   
  
  
  
  5.         return F(n-1)+F(n-2); 
    6.   
  
  
  
  6.     } 
    7.   
  
  
  
  7. } 
    8.

其實(shí)它的調(diào)用流程為：

不過這個(gè)斐波那契這樣的求法效率并不高，后面會(huì)提一嘴。

遞歸解決漢諾塔

漢諾塔是經(jīng)典遞歸問題：

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

  1. 如果A只有一個(gè)(A->C)
  2. 如果A有兩個(gè)(A->B),(A->C),(B->C)
  3. 如果A有三個(gè)(A->C),(A->B),(C->B),(A->C),(B->A),(B->C),(A->C).
  4. 如果更多，那么將會(huì)爆炸式增長(zhǎng)。

可以發(fā)現(xiàn)每增加一步，其中的步驟會(huì)多很多，如果一步步想，很難想明白，所以要用遞歸全局的想法看問題。

當(dāng)有1個(gè)要從A->C時(shí)，這里使用函數(shù)move(A,C)表示(其他move操作同理)。

用hannuo(n)函數(shù)表示總共n個(gè)盤子要從A->C。

遞歸，其實(shí)就是要找上下層的關(guān)系，n個(gè)盤子從A挪到C和n-1個(gè)盤子從A挪到C有啥聯(lián)系(hannuo(n)—>hannuo(n-1)有啥關(guān)系)。下面帶你一步步分析。

假設(shè)有n個(gè)盤子

hannuo(n-1)之后n-1個(gè)盤子從A—>C.

此時(shí)剩下底下最大的，只能移動(dòng)到B，move(A,B)

那么你是否發(fā)現(xiàn)什么眉目了，只需原先的huannuo(n-1)相同操作從C—>B即可完成轉(zhuǎn)移到B，所以這個(gè)需要加參數(shù)表示其方向性，那么我們的之前函數(shù)應(yīng)該寫成hannuo(n-1,A,C),但是這里肯定又用到B(向下需要用到)，所以把B傳進(jìn)來hannuo(n-1,A,B,C)先表示為從n-1個(gè)從A(借助B執(zhí)行若干操作)轉(zhuǎn)到C。

這一系列操作使得將n個(gè)盤子從A—>B但是我們要的是A—>C才是需要的hannuo(n,A,B,C)，這個(gè)很容易啊我們只需要第一步將n-1挪到B上就可以了啊。

經(jīng)過上面分析，那么完整的操作為：

 
 
 
 
      
  
  
  
  1. package 遞歸; 
    2.   
  
  
  
  2. public class hannuota { 
    3.   
  
  
  
  3.     static void move(char a,char b) 
    4.   
  
  
  
  4.     { 
    5.   
  
  
  
  5.         System.out.println("移動(dòng)最上層的"+ a+ "到"+ b+ "\t"); 
    6.   
  
  
  
  6.     } 
    7.   
  
  
  
  7.     static void hannuota(int n,char a,char b,char c)//主要分析每一大步對(duì)于下一步需要走的。 
    8.   
  
  
  
  8.     { 
    9.   
  
  
  
  9.         if(n==1) {move(a,c);}//從a移到c 
    10.   
  
  
  
  10.         else 
    11.   
  
  
  
  11.         { 
    12.   
  
  
  
  12.             hannuota(n-1,a,c,b);//將n-1個(gè)從a借助c移到b 
    13.   
  
  
  
  13.             move(a,c); //將第n（最后一個(gè)）從a移到c。 
    14.   
  
  
  
  14.             hannuota(n-1,b,a,c);//再將n-1個(gè)從b借助a移到c 
    15.   
  
  
  
  15.         } 
    16.   
  
  
  
  16.     } 
    17.   
  
  
  
  17.     public static void main(String[] args) 
    18.   
  
  
  
  18.     { 
    19.   
  
  
  
  19.  
    20.   
  
  
  
  20.         hannuota(5,'a','b','c'); 
    21.   
  
  
  
  21.     } 
    22.   
  
  
  
  22. } 
    23.

這樣，漢諾塔問題是不是搞懂了?

遞歸 VS 記憶化

很多時(shí)候，遞歸的效率是很低的(一個(gè)遞歸拆分成兩個(gè)及以上子問題效率就不太行了)，我們要用動(dòng)態(tài)規(guī)劃或者記憶化去優(yōu)化，為什么要記憶化?因?yàn)檫f歸成子問題，子問題再拆分成子問題，造成很多的重復(fù)計(jì)算!

比如上面說到的遞歸求斐波那契數(shù)列，就是一個(gè)效率非常低的算法，比如你看看F(5)是這樣走的：

在遞歸求F(4)時(shí)候，F(xiàn)(4)遞歸會(huì)求解F(3)，但是右側(cè)的還會(huì)再執(zhí)行一遍。如果是數(shù)量非常大的數(shù)，那么將耗費(fèi)很大的時(shí)間。所以我們就可以采取記憶化!第一次算出結(jié)果的時(shí)候就存儲(chǔ)一下，如果是線性有規(guī)律(大部分)就用數(shù)組，否則就用HashMap存儲(chǔ)。

具體實(shí)現(xiàn)的代碼為:

 
 
 
 
      
  
  
  
  1. static long F(int n,long record[]) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.   if(n==1||n==2) {return 1;} 
    4.   
  
  
  
  4.   if(record[n]>0) 
    5.   
  
  
  
  5.     return record[n]; 
    6.   
  
  
  
  6.   else 
    7.   
  
  
  
  7.     record[n]=F(n-1,record)+F(n-2,record); 
    8.   
  
  
  
  8.   return record[n]; 
    9.   
  
  
  
  9. } 
    10.   
  
  
  
  10. public static void main(String[] args) { 
    11.   
  
  
  
  11.   int n=6; 
    12.   
  
  
  
  12.   long[] record = new long[n+1]; 
    13.   
  
  
  
  13.   System.out.println(F(n,record)); 
    14.   
  
  
  
  14. } 
    15.

這樣可以節(jié)省很多時(shí)間，尤其是n非常大的情況(遞歸是指數(shù)級(jí)別增長(zhǎng)，記憶化是線性級(jí)別)。例如一個(gè)F(6)求解過程：

當(dāng)然，記憶化的問題遠(yuǎn)遠(yuǎn)不止這么多，具體還需要自行學(xué)習(xí)。

遞歸 VS 數(shù)據(jù)結(jié)構(gòu)

遞歸在很多場(chǎng)景都有很好的應(yīng)用，在鏈表中、二叉樹、圖中(搜索算法)都有很多的應(yīng)用，這里就舉一些非常經(jīng)典的例子。

比如在鏈表中，很經(jīng)典的就是鏈表逆序輸出、鏈表反轉(zhuǎn)問題，比如鏈表反轉(zhuǎn)問題，對(duì)應(yīng)力扣206(給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表)，可以這樣巧妙的實(shí)現(xiàn)：

 
 
 
 
      
  
  
  
  1. /** 
    2.   
  
  
  
  2.  * Definition for singly-linked list. 
    3.   
  
  
  
  3.  * public class ListNode { 
    4.   
  
  
  
  4.  *     int val; 
    5.   
  
  
  
  5.  *     ListNode next; 
    6.   
  
  
  
  6.  *     ListNode() {} 
    7.   
  
  
  
  7.  *     ListNode(int val) { this.val = val; } 
    8.   
  
  
  
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } 
    9.   
  
  
  
  9.  * } 
    10.   
  
  
  
  10.  */ 
    11.   
  
  
  
  11. class Solution { 
    12.   
  
  
  
  12.     public ListNode reverseList(ListNode head) { 
    13.   
  
  
  
  13.         if(head==null||head.next==null) 
    14.   
  
  
  
  14.             return  head; 
    15.   
  
  
  
  15.         ListNode node =reverseList(head.next);//返回最后的鏈表節(jié)點(diǎn) 
    16.   
  
  
  
  16.         head.next.next=head;//后一個(gè)節(jié)點(diǎn)指向自己 
    17.   
  
  
  
  17.         head.next=null;//自己next指向null  
    18.   
  
  
  
  18.         return node; 
    19.   
  
  
  
  19.     } 
    20.   
  
  
  
  20. } 
    21.

對(duì)于二叉樹，最經(jīng)典的就是二叉樹的前序、中序、后序遍歷的遞歸實(shí)現(xiàn)方式：

例如二叉樹前序遍歷：

 
 
 
 
      
  
  
  
  1. public void qianxu(node t)// 前序遞歸 前序遍歷：根結(jié)點(diǎn) ---> 左子樹 ---> 右子樹 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if (t != null) { 
    4.   
  
  
  
  4.         System.out.print(t.value + " ");// 當(dāng)前節(jié)點(diǎn) 
    5.   
  
  
  
  5.         qianxu(t.left); 
    6.   
  
  
  
  6.         qianxu(t.right); 
    7.   
  
  
  
  7.     } 
    8.   
  
  
  
  8. } 
    9.

二叉樹中序遍歷：

 
 
 
 
      
  
  
  
  1. public void zhongxu(node t)// 中序遍歷 中序遍歷：左子樹---> 根結(jié)點(diǎn) ---> 右子樹 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if (t != null) { 
    4.   
  
  
  
  4.         zhongxu(t.left); 
    5.   
  
  
  
  5.         System.out.print(t.value + " ");// 訪問完左節(jié)點(diǎn)訪問當(dāng)前節(jié)點(diǎn) 
    6.   
  
  
  
  6.         zhongxu(t.right); 
    7.   
  
  
  
  7.     } 
    8.   
  
  
  
  8. } 
    9.

二叉樹的后序遍歷：

 
 
 
 
      
  
  
  
  1. public void houxu(node t)// 后序遍歷 后序遍歷：左子樹 ---> 右子樹 ---> 根結(jié)點(diǎn) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if (t != null) { 
    4.   
  
  
  
  4.         houxu(t.left); 
    5.   
  
  
  
  5.         houxu(t.right); 
    6.   
  
  
  
  6.         System.out.print(t.value + " "); // 訪問玩左右訪問當(dāng)前節(jié)點(diǎn) 
    7.   
  
  
  
  7.     } 
    8.   
  
  
  
  8. } 
    9.

遞歸 VS 常見算法在我們熟知很多算法都與遞歸有著很大關(guān)系。比如dfs深度優(yōu)先遍歷、回溯算法、分治算法等，這里只是簡(jiǎn)單介紹一下。

遞歸只是計(jì)算機(jī)執(zhí)行一種方式，一個(gè)來回的過程，所以這個(gè)過程可以被一些算法很巧妙的運(yùn)用。

分治算法：將問題分解成多個(gè)子問題，子問題求解完合并得到結(jié)果，這個(gè)過程可以使用遞歸實(shí)現(xiàn)(也可能不使用遞歸)，但大部分會(huì)用遞歸因?yàn)閷?shí)現(xiàn)更加簡(jiǎn)潔，它和斐波那契遞歸不同的是它分裂的子問題一般沒有重復(fù)的(即分完為止而不會(huì)重復(fù)計(jì)算)。常見的快排、歸并排序都是使用分治算法，其算法實(shí)現(xiàn)借助遞歸。例如歸并排序其流程：

算法實(shí)現(xiàn)為：

 
 
 
 
      
  
  
  
  1. private static void mergesort(int[] array, int left, int right) { 
    2.   
  
  
  
  2.   int mid=(left+right)/2; 
    3.   
  
  
  
  3.   if(left  
  
  
  
  4.   { 
    5.   
  
  
  
  5.     mergesort(array, left, mid); 
    6.   
  
  
  
  6.     mergesort(array, mid+1, right); 
    7.   
  
  
  
  7.     merge(array, left,mid, right); 
    8.   
  
  
  
  8.   } 
    9.   
  
  
  
  9. } 
    10.   
  
  
  
  10.  
    11.   
  
  
  
  11. private static void merge(int[] array, int l, int mid, int r) { 
    12.   
  
  
  
  12.   int lindex=l;int rindex=mid+1; 
    13.   
  
  
  
  13.   int team[]=new int[r-l+1]; 
    14.   
  
  
  
  14.   int teamindex=0; 
    15.   
  
  
  
  15.   while (lindex<=mid&&rindex<=r) {//先左右比較合并 
    16.   
  
  
  
  16.     if(array[lindex]<=array[rindex]) 
    17.   
  
  
  
  17.     { 
    18.   
  
  
  
  18.       team[teamindex++]=array[lindex++]; 
    19.   
  
  
  
  19.     } 
    20.   
  
  
  
  20.     else {                 
    21.   
  
  
  
  21.       team[teamindex++]=array[rindex++]; 
    22.   
  
  
  
  22.     } 
    23.   
  
  
  
  23.   } 
    24.   
  
  
  
  24.   while(lindex<=mid)//當(dāng)一個(gè)越界后剩余按序列添加即可 
    25.   
  
  
  
  25.   { 
    26.   
  
  
  
  26.     team[teamindex++]=array[lindex++]; 
    27.   
  
  
  
  27.  
    28.   
  
  
  
  28.   } 
    29.   
  
  
  
  29.   while(rindex<=r) 
    30.   
  
  
  
  30.   { 
    31.   
  
  
  
  31.     team[teamindex++]=array[rindex++]; 
    32.   
  
  
  
  32.   }     
    33.   
  
  
  
  33.   for(int i=0;i  
  
  
  
  34.   { 
    35.   
  
  
  
  35.     array[l+i]=team[i]; 
    36.   
  
  
  
  36.   } 
    37.   
  
  
  
  37.  
    38.   
  
  
  
  38. } 
    39.

dfs、回溯法 通常想著枚舉盡可能多的情況,很多時(shí)候我們并不能很好知道運(yùn)行界限是在哪，并且運(yùn)行中狀態(tài)可能會(huì)有所變化，所以我們可以寫好限定條件使用遞歸去實(shí)現(xiàn)，遞歸的歸過程也可很好的復(fù)原去進(jìn)行其他試探。包括二叉樹的前中后遍歷都蘊(yùn)涵dfs算法思想,而回溯算法則是經(jīng)典全排列、八皇后問題代表。

其流程通常為：

 
 
 
 
      
  
  
  
  1. 定義回溯算法及參數(shù) 
    2.   
  
  
  
  2. - (符合條件)跳出 
    3.   
  
  
  
  3. - (不符合)不跳出： 
    4.   
  
  
  
  4. - - 遍歷需要操作的列表&&該元素可操作&&可以繼續(xù)試探 
    5.   
  
  
  
  5. - - - 標(biāo)記該元素已使用以及其他操作 
    6.   
  
  
  
  6. - - - 遞歸調(diào)用(參數(shù)改變) 
    7.   
  
  
  
  7. - - - 清除該元素標(biāo)記以及其他操作 
    8.

此外，遞歸還在很多算法中有廣泛的應(yīng)用，這里就不具體列舉啦!

結(jié)語

今天遞歸就講到這里啦，學(xué)好遞歸沒那么容易，還是要具體掌握各種算法、題目才能慢慢領(lǐng)略遞歸精髓，遞歸用好可以寫出很多騷代碼!

不過實(shí)際題目注重效率和便捷，不能盲目追求效率，也不能盲目使用遞歸不注意算法優(yōu)化。


分享標(biāo)題：寫給小白看的遞歸(硬核)
地址分享：http://m.5511xx.com/article/cdjohio.html