你真的瞭解遞迴嗎？

遞迴數列是什麼意思

文末有驚喜哦！

1。什麼是遞迴

任何呼叫自身的函式稱為遞迴。用遞迴方法求解問題，要點在於遞迴函式呼叫自身去解決一個規模比原始問題小一些的問題。這個過程稱為遞迴步驟。遞迴步驟會導致更多的遞迴呼叫。因此，保證遞迴過程能夠終止是很重要的。每次函式都會用比原問題規模更小的問題來呼叫自身。問題隨著規模不斷變小必須能最終收斂到基本情形。

2。為什麼要用遞迴

遞迴是從數學領域借鑑過來的一種有用的技術。遞迴程式碼通常比迭代程式碼更加簡潔易懂。一般來說，在編譯或解釋時，迴圈會轉化為遞迴函式。當任務能夠被相似的子任務定義時，採用遞迴處理十分有效。例如，排序、搜尋和遍歷等問題往往有更簡潔的遞迴解決方案。

3。遞迴和記憶體（視覺化）

每次遞迴呼叫都在記憶體中生成一個新的函式副本（實際上僅僅是一些相關的變數）。一旦函式結束（即返回某些資料），該返回函式的副本就從記憶體中刪除。

4。遞迴與迭代

在討論遞迴的時候，會有一個基本的問題是遞迴和迭代哪種方法更好？這個問題的答案取決於我們想做什麼。遞迴方法透過類似映象的方式來解決問題。當問題沒有明顯的答案時，遞迴方法透過簡化問題來解決它。但是，每次遞迴呼叫都會增加開銷（棧需要空間開銷）。

遞迴：

當達到基本情形時，遞迴終止。

每次遞迴調都需要額外的空間用於棧幀（記憶體）開銷。

如果出現無窮遞迴，程式可能會耗盡記憶體，並出現棧溢位。

某些問題採用遞迴方法更容易解決。

迭代：

當迴圈條件為假時，迭代終止。

每次迭代不需要任何額外的空間開銷。

由於沒有額外的空間開銷，所以若出現死迴圈，則程式會一直迴圈執行。

採用迭代求解問題可能沒有遞迴解決方案那樣顯而易見

5。遞迴說明

遞迴演算法有兩類情形：遞迴情形和基本情形。

每個遞迴函式必須終止於基本情形。

通常，迭代解決方案比遞迴解決方案更加有效（因為後者有函式呼叫的開銷）。

一個遞迴演算法可以透過使用棧代替遞迴函式的方式來實現，但通常是得不償失的。這意味著任何能用遞迴求解的問題也能用迭代來求解。

對於某些問題，沒有明顯的迭代求解演算法。

有些問題非常適合用遞迴來求解，而有些則不適合。

6。遞迴演算法的經典用例

6.1斐波那契數列

斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波納契數列以如下被以遞推的方法定義：F（1）=1，F（2）=1， F（n）=F（n-1）+F（n-2）（n>=3，n∈N*）在現代物理、準晶體結構、化學等領域，斐波納契數列都有直接的應用，為此，美國數學會從1963年起出版了以《斐波納契數列季刊》為名的一份數學雜誌，用於專門刊載這方面的研究成果。

public class FibonacciDemo { // 全域性變數sum1記錄第一個方法呼叫的次數，sum2記錄第二個方法呼叫的次數 static int sum1； static int sum2； public static void main（String［］ args） { // n代表數列的長度、 a代表數列的第一項、 b代表數列的第二項 int n = 10； int a = 1； int b = 1； long algResult = fibonacci（n）； // 使用未最佳化的遞迴演算法得到值 System。out。println（“使用未最佳化的遞迴演算法得到值：” + algResult + “方法呼叫次數為：” + sum1）； // 使用最佳化的遞迴演算法，減少冗餘的方法呼叫得到的值 long algEvoResult = fibonacciEvolution（a， b， n）； System。out。println（“使用已經最佳化的遞迴演算法得到值：” + algEvoResult + “方法呼叫次數為：” + sum2）； } public static long fibonacci（int n） { // 記錄呼叫方法次數 sum1++； if （n < 2） { return n； } return fibonacci（n - 1） + fibonacci（n - 2）； } public static long fibonacciEvolution（int a， int b， int n） { // 記錄呼叫方法次數 sum2++； if （n > 2） { return fibonacciEvolution（a + b， a， n - 1）； } return a； }}

6.2階層

階層是基斯頓·卡曼（Christian Kramp，1760～1826）於 1808 年發明的運算子號，是數學術語。一個正整數的階乘（factorial）是所有小於及等於該數的正整數的積，並且0的階乘為1。自然數n的階乘寫作n！。1808年，基斯頓·卡曼引進這個表示法。亦即n！=1×2×3×。。。×n。階乘亦可以遞迴方式定義：0！=1，n！=（n-1）！×n。

public class FactorialDemo { // 全域性變數sum，記錄方法呼叫的次數 static int sum； public static void main（String［］ args） { int n = 10； int result = factorial（n）； System。out。println（“n的階乘為：” + result + “；呼叫方法次數為：” + sum）； } public static int factorial（int n） { sum++； // 0 和 1 的階乘都是1 if （n == 1 || n == 0） { return 1； } int result = n * factorial（n - 1）； return result； }}

6.3歸併排序

歸併排序（MERGE-SORT）是建立在歸併操作上的一種有效的排序演算法，該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。用途：（速度僅次於快速排序，為穩定排序演算法，一般用於對總體無序，但是各子項相對有序的數列，應用見2011年普及複賽第3題“瑞士輪”的標程）

public class MergingSortDemo {//privatestaticlongsum=0； /** * *

     * *二路歸併     * *原理：將兩個有序表合併和一個有序表     * *

* * * *@parama * *@params * *第一個有序表的起始下標 * *@paramm * *第二個有序表的起始下標 * *@paramt * *第二個有序表的結束下標 * * */ private static void merge（int［］ a， int s， int m， int t） { int［］ tmp = new int［t - s + 1］； int i = s， j = m， k = 0； while （i < m && j <= t） { if （a［i］ <= a［j］） { tmp［k］ = a［i］； k++； i++； } else { tmp［k］ = a［j］； j++； k++； } } while （i < m） { tmp［k］ = a［i］； i++； k++； } while （j <= t） { tmp［k］ = a［j］； j++； k++； } System。arraycopy（tmp， 0， a， s， tmp。length）； } /** * * * *@parama * *@params * *@paramlen * *每次歸併的有序集合的長度 */ public static void mergeSort（int［］ a， int s， int len） { int size = a。length； int mid = size / （len << 1）； int c = size & （（len << 1） - 1）； //————-歸併到只剩一個有序集合的時候結束演算法————-// if （mid == 0） return； //————進行一趟歸併排序————-// for （int i = 0； i < mid； ++i） { s = i * 2 * len； merge（a， s， s + len，（len << 1） + s - 1）； } //————-將剩下的數和倒數一個有序集合歸併————-// if （c ！= 0） merge（a， size - c - 2 * len， size - c， size - 1）； //————-遞迴執行下一趟歸併排序————// mergeSort（a， 0， 2 * len）； } public static void main（String［］ args） { int［］ a = new int［］{4， 3， 6， 1， 2， 5}； mergeSort（a， 0， 1）； for （int i = 0； i < a。length； ++i） { System。out。print（a［i］ + “”）； } }}

6.4快速排序

快速排序（Quicksort）是對氣泡排序的一種改進。快速排序由C。 A。 R。 Hoare在1962年提出。它的基本思想是：透過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分別進行快速排序，整個排序過程可以遞迴進行，以此達到整個資料變成有序序列。

public class QuickSortDemo { // 分割槽 private static int partition（int［］ arr， int start， int end） { // 得到陣列中第一個元素的值 int key = arr［start］； // 判斷陣列長度 while （start < end） { while （arr［end］ >= key && end > start） end——； arr［start］ = arr［end］； while （arr［start］ <= key && end > start） start++； arr［end］ = arr［start］； } arr［start］ = key； return start； } // 快排 public static void quickSort（int arr［］， int start， int end） { if （start < end） { int index = partition（arr， start， end）； // 遞迴呼叫 quickSort（arr， start， index - 1）； quickSort（arr， index + 1， end）； } } // 測試 public static void main（String［］ args） { int arr［］ = {12， 32， 41， 90， 8， 68， 44， 31， 33， 9}； // start：arr陣列第一個元素的下標 // end ：arr陣列最後一個元素的下標 int start = 0； int end = arr。length - 1； quickSort（arr， start， end）； System。err。println（“排序後為：” + Arrays。toString（arr））； }}

6.5二分查詢

二分查詢也稱折半查詢（Binary Search），它是一種效率較高的查詢方法。但是，折半查詢要求線性表必須採用順序儲存結構，而且表中元素按關鍵字有序排列。

public class BinarySearchDemo { public static void main（String［］ args） { int［］ arr = {1， 3， 5， 7， 9， 11}； int key = 11； int index = binarySearch（arr， key）； System。out。println（“二分查詢元素的下標為：” + index）； int index1 = recursionBinarySearch（arr， key - 2， 0， arr。length - 1）； System。out。println（“遞迴二分查詢元素的下標為：” + index1）； } // 二分查詢 key為目標元素返回查詢元素的下標 public static int binarySearch（int arr［］， int key） { int low = 0； int high = arr。length - 1； int middle； while （low <= high） { middle = （low + high） / 2； if （arr［middle］ > key） { // 比關鍵字大則關鍵字在左區域 high = middle - 1； } else if （arr［middle］ < key） { // 比關鍵字小則關鍵字在右區域 low = middle + 1； } else { return middle； } } System。err。println（“不存在此元素”）； return -1； } // 遞迴實現二分查詢 public static int recursionBinarySearch（int［］ arr， int key， int low， int high） { if （key < arr［low］ || key > arr［high］ || low > high） { return -1； } int middle = （low & high） + （（low ^ high） >> 1）； //初始中間位置 if （arr［middle］ > key） { //比關鍵字大則關鍵字在左區域 return recursionBinarySearch（arr， key， low， middle - 1）； } else if （arr［middle］ < key） { //比關鍵字小則關鍵字在右區域 return recursionBinarySearch（arr， key， middle + 1， high）； } else { return middle； } }}

6.6樹的遍歷和許多樹的問題：中序遍歷、前序遍歷、後序遍歷

package com。wxt。recursive；import com。wxt。pojo。Node；/** * @description：使用遞迴方法演示前序、中序、後續遍歷 * @author： Mr。Wang * @create： 2019-01-04 22：58 **/public class BinaryTree { public Node init（） { //注意必須逆序建立，先建立子節點，再逆序往上建立，因為非葉子結點會使用到下面的節點，而初始化是按順序初始化的，不逆序建立會報錯 Node J = new Node（8， null， null）； Node H = new Node（4， null， null）； Node G = new Node（2， null， null）； Node F = new Node（7， null， J）； Node E = new Node（5， H， null）； Node D = new Node（1， null， G）； Node C = new Node（9， F， null）； Node B = new Node（3， D， E）； Node A = new Node（6， B， C）； //返回根節點 return A； } // 得到當前節點 public void printNode（Node node） { int data = node。getData（）； String result = String。valueOf（data）； System。out。print（result）； } // The former sequence traversal - 前序遍歷 public void firstTraversal（Node root） { printNode（root）； // 使用遞迴演算法遍歷左節點 if （root。getLeftNode（）！= null） { firstTraversal（root。getLeftNode（））； } // 使用遞迴演算法遍歷右節點 if （root。getRightNode（）！= null） { firstTraversal（root。getRightNode（））； } } // In the sequence traversal - 中序遍歷 public void inOtherTraversal（Node root） { if （root。getRightNode（）！= null） { inOtherTraversal（root。getRightNode（））； } printNode（root）； if （root。getLeftNode（）！= null） { inOtherTraversal（root。getLeftNode（））； } } // The former sequence traversal - 後續遍歷 public void postOtherTraversal（Node root） { if （root。getRightNode（）！= null） { postOtherTraversal（root。getRightNode（））； } if （root。getLeftNode（）！= null） { postOtherTraversal（root。getLeftNode（））； } printNode（root）； } public static void main（String［］ args） { BinaryTree tree = new BinaryTree（）； // 初始化二叉樹 Node root = tree。init（）； System。out。println（“先序遍歷：”）； tree。firstTraversal（root）； System。out。println（“”）； System。out。println（“中序遍歷：”）； tree。inOtherTraversal（root）； System。out。println（“”）； System。out。println（“後序遍歷：”）； tree。postOtherTraversal（root）； System。out。println（“”）； }}

由於篇幅有限，如果您想要獲取到

免費

的JAVA技術乾貨的話，關注我後私信請傳送“資料”給我噢！記得幫助小編點贊文章哦！

真誠分享，不要吝嗇您的贊哦！

免費！免費！免費！重要的事情說三遍！！！