🍅 作者主頁(yè)：Roninaxious
🍅 歡迎點(diǎn)贊 👍 收藏 ?留言 📝

🚢前言

🎐何為遞歸

遞歸顧名思義就是′遞′和′歸′

👀所謂的‘遞’也就是“向下遞去”，這個(gè)問題可以分解為若干個(gè)且形式相同的子問題，這些子問題可以使用相同的思路來解決。

👀所謂的‘歸’也就是“歸來的意思”，什么時(shí)候歸來？所以涉及到了臨界點(diǎn)，也就是‘遞’中的分解終止條件。

🎐遞歸的工作原理

💦根據(jù)遞歸兩字的含義，不難發(fā)現(xiàn)，它包含了遞去和歸來兩個(gè)層面。

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

🎐遞歸 == 數(shù)學(xué)歸納法 ？

眾所周知，計(jì)算機(jī)是數(shù)學(xué)的一個(gè)分支。這是一個(gè)不可否認(rèn)的問題，在編程過程中，我們總能在數(shù)學(xué)中找到答案。遞歸提高了代碼的可讀性，但同時(shí)加大了內(nèi)存的消耗，遞歸讓人又愛又恨；不可否認(rèn)，遞歸很重要！那么它和數(shù)學(xué)歸納法有什么聯(lián)系呢？

💦歸納法
對(duì)于一個(gè)命題S(n)，n為大于0的自然數(shù)；如何證明命題成立呢？

👀1.當(dāng)n=1時(shí)，命題成立
👀2.當(dāng)n=k時(shí)，命題成立
👀3.證明n=k+1時(shí)命題也成立

🧧遞歸本質(zhì)上是類似歸納法，但又有點(diǎn)稍微不同🧧

遞歸是從F(n)倒推到F(1),然后在F(1)回溯到F(n)；相比于歸納法多了一步。

---

💟 對(duì)于遞歸你了解多少了呢？💟

• 🚢前言
• • 🎐何為遞歸
  • 🎐遞歸的工作原理
  • 🎐遞歸 == 數(shù)學(xué)歸納法 ？
• 🚢如何正確使用遞歸
• • 🎐遞歸常用流程
  • 🎐遞歸的三大要素
  • • 💥1、縮小問題規(guī)模
    • 💥2、明確遞歸終止條件
    • 💥3、給出遞歸終止時(shí)的處理辦法
• 🚢經(jīng)典問題一之迷宮求解
• • 🎐迷宮求解流程分析
  • 🎐源代碼
• 🚢經(jīng)典問題二之鏈表反轉(zhuǎn)一(全反轉(zhuǎn))
• • 🎐鏈表反轉(zhuǎn)流程分析
  • 🎐源代碼
• 🚢經(jīng)典問題二之鏈表反轉(zhuǎn)二(反轉(zhuǎn)前n個(gè)節(jié)點(diǎn))
• • 🎐鏈表反轉(zhuǎn)2流程分析
  • 🎐源代碼
• 🚢經(jīng)典問題二之鏈表反轉(zhuǎn)三(反轉(zhuǎn)中間部分)

---

🚢如何正確使用遞歸

使用遞歸需要注意很多點(diǎn)，否者造成無限遞歸?就是在造孽了

🎐遞歸常用流程

* void func(mode)* {* if(endCondition) //臨界條件* {* constExpression //處理方法* }* else* {* accumrateExpreesion //歸納項(xiàng)* mode=expression //步進(jìn)表達(dá)式* func(mode) //調(diào)用本身，遞歸* }* }

🙄注意一定不要在自己腦子里遞來遞去的，你的腦子能壓幾個(gè)棧呢，否者很容易就陷入死腦筋之中🙄

🎐遞歸的三大要素

💥1、縮小問題規(guī)模

👀這個(gè)縮小問題規(guī)模可以根據(jù)歸納法先進(jìn)行回推，比如讓求S(n),我們可以先求當(dāng)n=1的解決方法，再求n=2時(shí)的解決方法…一直歸納到S(n)；這樣我們就可以推導(dǎo)出關(guān)系式S(n)=S(n-1)+?

稍后會(huì)根據(jù)經(jīng)典問題思考如何縮小問題規(guī)模。

💥2、明確遞歸終止條件

👀遞歸既然有去有回，就必須有一個(gè)臨界條件，當(dāng)程序到達(dá)這個(gè)臨界值就必須進(jìn)行歸來；否者就肯定會(huì)造成無線遞歸下去，什么棧也扛不住！

💥3、給出遞歸終止時(shí)的處理辦法

👀根據(jù)上文中闡述的遞歸的工作原理，遞歸是通過棧來實(shí)現(xiàn)的；當(dāng)程序到達(dá)臨界條件時(shí)，后續(xù)必須進(jìn)行出棧。了解函數(shù)的壓棧和出棧過程，函數(shù)出棧也就是返回到上一個(gè)函數(shù)的調(diào)用處繼續(xù)執(zhí)行。例如求解F(n)，遞推式是F(n)=F(n-1)+F(n-2)，終止條件F(1)=1，F(0)=0；它的流程是每次進(jìn)行壓棧F(n-1)、F(n-2)，當(dāng)達(dá)到終止條件時(shí)進(jìn)行函數(shù)的出棧，那么返回什么值呢？根據(jù)遞歸的倒數(shù)第一步F(2)=F(1)+F(0)所以返回的是F(1)+F(0),也就是1.

🚢經(jīng)典問題一之迷宮求解

?問題描述?

• 找到迷宮路出口

🎐迷宮求解流程分析

右下角為迷宮的出口，方塊為墻，圓形塊為迷宮入口；如何找到一條通路從入口到出口？

🎈為了表示方便，我以二位數(shù)組為例進(jìn)行操作。擬定二位數(shù)組中的1代表墻，2代表通路，3代表路已經(jīng)走過且不通，0代表未走過的路。

?? 初始化迷宮

📑首先迷宮有四個(gè)方向可以走(上下左右），所以我們應(yīng)該先自定義一個(gè)策略，規(guī)定?下右上左?(優(yōu)先走下，然后右->上->左），也就是當(dāng)下不通時(shí)，走右…

🎆根據(jù)遞歸三要素

1.分解成子問題

2.遞歸終止條件

這個(gè)當(dāng)然就是出口了，也就是map[5][6] == 2;

🎐源代碼

public class Labyrinth {private static final int X_MAX = 7;private static final int Y_MAX = 8;private static int[][] map = new int[X_MAX][Y_MAX];/*** 迷宮問題--遞歸* 思路：* 策略：規(guī)定下右上左為行走策略* 1代表障礙物,2代表走過的路,3代表路已經(jīng)走過且不通,0代表未走過的路*/public static boolean setWays(int[][] arr, int x, int y) {if (arr[5][6] == 2) { //終止條件return true;} else {if (arr[x][y] == 0) {arr[x][y] = 2;if (setWays(arr, x, y + 1)) { //下return true;} else if (setWays(arr, x + 1, y)) { //右return true;} else if (setWays(arr, x, y - 1)) { //上return true;} else if (setWays(arr, x - 1, y - 1)) {//左return true;} else { //如果下右上左都不能走，所以此路不同，置為3arr[x][y] = 3;return false;}} else { //arr[x][y] != 0 ? 有可能是1,2,3return false;}}}//測(cè)試public static void main(String[] args) {for (int i = 0; i < X_MAX; i++) {map[i][0] = 1;map[i][Y_MAX - 1] = 1;}for (int j = 1; j < Y_MAX - 1; j++) {map[0][j] = 1;map[X_MAX - 1][j] = 1;}map[1][2] = 1;map[1][3] = 1;map[2][3] = 1;map[3][3] = 1;map[3][2] = 1;setWays(map, 1, 1);printMap(map);}//打印迷宮地圖public static void printMap(int[][] arr) {for (int j = 0; j < Y_MAX; j++) {for (int i = 0; i < X_MAX; i++) {System.out.print(arr[i][j] + " ");}System.out.println();}} }

?? 運(yùn)行結(jié)果

🚢經(jīng)典問題二之鏈表反轉(zhuǎn)一(全反轉(zhuǎn))

🔰問題描述🔰

• 給定一個(gè)鏈表，將其反轉(zhuǎn)
• 例如：1->2->3->4 ---- 4->3->2->1

🎐鏈表反轉(zhuǎn)流程分析

📑對(duì)于該問題，將其整體分為兩部分1和n-1，將其反轉(zhuǎn)即可；然后再將n-1部分整體分為兩部分，再將其反轉(zhuǎn)即可。

🎆根據(jù)遞歸三要素

1.分解成子問題

2.遞歸終止條件

對(duì)于這個(gè)終止條件，這個(gè)應(yīng)該比較簡(jiǎn)單，當(dāng)遞歸到最后一個(gè)節(jié)點(diǎn)時(shí)開始進(jìn)行歸來操縱，也就是head.next == null || head == null；對(duì)于這個(gè)head == null是因?yàn)榭真湵淼那闆r。

3.遞歸終止處理辦法

由于我們最后反轉(zhuǎn)鏈表之后，要將最后一個(gè)節(jié)點(diǎn)定義為頭節(jié)點(diǎn)。所以需要將該節(jié)點(diǎn)返回。

if (head == null || head.next == null) {return head;}

🎐源代碼

package com.zsh.algorithm.recursion;/*** @author:Ronin* @since:2021/9/16* @email:1817937322@qq.com*//*** 反轉(zhuǎn)單鏈表 question one* eg：1->2->3->4 ---- 4->3->2->1*/ public class ReverseLinkedList {/*** 鏈表反轉(zhuǎn)* 思路：將鏈表分成兩部分（1.第一個(gè)頭節(jié)點(diǎn) 2.頭節(jié)點(diǎn)之后的所有）* 遞歸回溯時(shí)將指針反轉(zhuǎn)即可* 遞歸出口條件：head || head.next == null* @param head* @return*/static Node reverse(Node head) {if (head == null || head.next == null) {return head;}Node currentNode = reverse(head.next);head.next.next = head;head.next = null;return currentNode;}// public static void main(String[] args) { // Node node = new Node(1); // Node node2 = new Node(2); // Node node3 = new Node(3); // LinkedListNode linkedListNode = new LinkedListNode(); // linkedListNode.add(node); // linkedListNode.add(node2); // linkedListNode.add(node3); // Node reverseHead = reverse(linkedListNode.head); // linkedListNode.print(reverseHead); // } }//class Node { // int num; // Node next; // public Node() {} // public Node(int i) { // this.num = i; // } //} //class LinkedListNode { // Node head = null; // // public void add(Node addNode) { // if (head == null) { // head = addNode; // return; // } // Node temp = head; // while (temp.next != null) { // temp = temp.next; // } // temp.next = addNode; // temp = addNode; // temp.next = null; // } // // public void print(Node reverseHead) { // Node temp = reverseHead; // while (temp != null) { // System.out.print(temp.num); // System.out.print("->"); // temp = temp.next; // } // } //}

🚢經(jīng)典問題二之鏈表反轉(zhuǎn)二(反轉(zhuǎn)前n個(gè)節(jié)點(diǎn))

🔰問題描述🔰

• 反轉(zhuǎn)單鏈表2
• 反轉(zhuǎn)前n個(gè)節(jié)點(diǎn) 1->2->3->4->5->6
• reverse(node head, 3)
• 3->2->1->4->5->6

🎐鏈表反轉(zhuǎn)2流程分析

如果已經(jīng)了解了全部節(jié)點(diǎn)的鏈表反轉(zhuǎn)，那么這個(gè)應(yīng)該也比較簡(jiǎn)單；反轉(zhuǎn)前n個(gè)節(jié)點(diǎn)，當(dāng)然就是臨界條件改變了。全部節(jié)點(diǎn)的反轉(zhuǎn)是在最后一個(gè)節(jié)點(diǎn)作為臨界值，而這個(gè)只需要加入一個(gè)新的變量n進(jìn)行控制前n個(gè)節(jié)點(diǎn)反轉(zhuǎn)即可。

下圖是出棧得流程

🎐源代碼

public class ReverseLinkedListFront {static Node cur = null;static Node reverse(Node head, int n) {if (n <= 1 || head.next == null) {cur = head.next;return head;}Node lastNode = reverse(head.next, n-1);head.next.next = head;head.next = cur;return lastNode;}// public static void main(String[] args) { // Node node = new Node(1); // Node node2 = new Node(2); // Node node3 = new Node(3); // LinkedListNode linkedListNode = new LinkedListNode(); // linkedListNode.add(node); // linkedListNode.add(node2); // linkedListNode.add(node3); // Node reverseHead = reverse(linkedListNode.head, 3); // linkedListNode.print(reverseHead); // } }

🚢經(jīng)典問題二之鏈表反轉(zhuǎn)三(反轉(zhuǎn)中間部分)

對(duì)于1->2->3->4->5，我們將m=2,n=4進(jìn)行反轉(zhuǎn)
結(jié)果1->4->3->2->5

思路：
1.對(duì)于反轉(zhuǎn)（m~n），如果m=1也就是前n個(gè)節(jié)點(diǎn)反轉(zhuǎn)。
2.frontHead.next = reverse(frontHead.next, m-1, n-1);這一行代碼是最難理解的。m-1代表每次frontHead.next，當(dāng)m=1時(shí)，就到達(dá)了鏈表反轉(zhuǎn)部分的起點(diǎn)；n-1是因?yàn)?例如m=2，n=5，只反轉(zhuǎn)n-m=3個(gè)節(jié)點(diǎn)）。
3.return reverse(frontHead, n);會(huì)將中間(m~n)個(gè)節(jié)點(diǎn)進(jìn)行反轉(zhuǎn)
4.在第三步遞歸結(jié)束之后會(huì)返回到這一步frontHead.next =reverse(frontHead.next, m-1, n-1); 開始從m=3進(jìn)行回溯，直到m=1.回溯時(shí)進(jìn)行連接
5.該題非常考驗(yàn)遞歸解題能力.

public class ReverseLinkedListMid {static Node cur = null;static Node reverse(Node frontHead, int m, int n) {if (m == 1) {/*** 將局部進(jìn)行反轉(zhuǎn)，并與尾節(jié)點(diǎn)部分進(jìn)行連接*/return reverse(frontHead, n);}/*** 1-》2-》3-》4-》5 ==》 1-》2-》4-》3-》5* 在上一步【return reverse(frontHead, n)】返回的是反轉(zhuǎn)之后的頭節(jié)點(diǎn)，也就是4節(jié)點(diǎn)* 這一步是為了將2節(jié)點(diǎn)連接4、1節(jié)點(diǎn)連接2...*/frontHead.next = reverse(frontHead.next, m-1, n-1);return frontHead;}//局部反轉(zhuǎn)方法static Node reverse(Node head, int n) {if (n == 1 || head.next == null) {cur = head.next;return head;}Node lastNode = reverse(head.next, n - 1);head.next.next = head;head.next = cur;return lastNode;}public static void main(String[] args) {Node node = new Node(1);Node node2 = new Node(2);Node node3 = new Node(3);Node node4 = new Node(4);Node node5 = new Node(5);LinkedListNode linkedListNode = new LinkedListNode();linkedListNode.add(node);linkedListNode.add(node2);linkedListNode.add(node3);linkedListNode.add(node4);linkedListNode.add(node5);Node reverseHead = reverse(linkedListNode.head, 3, 4);linkedListNode.print(reverseHead);} }

飛速總結(jié)中…

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的【☀️~爆肝万字总结递归~❤️玩转算法系列之我如何才能掌握递归解题的能力❤️~十大经典问题助你突破极限~建议收藏☀️】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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