溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“怎么寫好java遞歸函數”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“怎么寫好java遞歸函數”吧!
寫遞歸，就是寫三要素的實現，三要素分別為函數，邊界，遞推公式，剛開始只要記住要這么寫，寫幾個算法之后，就能慢慢明白為什么要這樣搞。
明確你的函數是干什么用的，函數的入參應該是什么，返回值是什么，這三個問題，先從函數是干什么用的開始，你可以定義一個函數f() 假設已經實現了每一步遞歸的實現，再去明確這個實現 到底做了什么，入參至少要什么，返回值和參數返回可以理解為是一個東西，都是為了返回給上層調用或者全局的一個數據，想清楚函數的三個要素，那你的函數就定義好了。
同樣，先這樣去做，再去想為什么，這一步要判斷的就是函數的入參，入參的null ，入參為初始值，比如斐波那契數列的前1位或者2位，開始時候可能不一定想的完全，那沒關系，下面的一步還會繼續完善，所以我這里舉得例子是斐波那契的前1或2位，而不是直接說結論，這一步驟是在函數的實現里面，所以考慮方式就是假設，入參到了臨界值或者初始值，或者特殊值，你要判斷一下，第一遍寫的時候比如斐波那契，可以直接這么寫
if (n == 1) return 1; if (n == 2) return 1;
想到的不一定完全對，或者那么地很優雅， 沒關系，只要想到要考慮邊界就可以了。下面就是想邊界的意義是什么？有兩點，其一，異常值邊界，其二遞歸結束判斷，比如此題中的n < 0 怎么辦，和 n == 1 和 n == 2 就分別對應前面說的，當然這兩點可能考慮不那么完全，假設你只考慮了像前面代碼中的，或者寫邊界時候發現寫的多了，或者冗余了，這樣不影響程序的結果，那么寫完遞推公式，我們再來回顧邊界問題。
這個就要先談意義，再談實現了，意義在于逐漸減少算法的規模，或者定義一種方式讓輸入的值盡可能地靠近臨界值，也就是找一個關系f(n) 與 f(n-x)序列的關系，f(n) 代表要解決的問題規模，f(n-x) 比n小的問題規模的函數值，這是遞歸函數中的關鍵一步，沒有遞推公式，就沒有遞歸。例如斐波那契序列，中的遞推公式是f(n)=f(n-1) + f(n-2)我們來觀察這個公式，發現其第n 于 n-1 和 n-2 有關系，所以我們來看，如果輸入任何整數，那么n-1,n-2 可能取值是負數，0，1+，可以看到邊界0和負數沒有考慮在內，所以，這時回顧前面1.2 的遞歸，我們來補充一下邊界后得到：
if (n <= 2) return 1;
下面通過三個簡單例子，我們來練習使用遞歸，分別是青蛙跳臺階問題，等同于斐波那契序列，遞歸方式反轉單鏈表，遞歸遍歷樹，以及針對三個
第一定義函數,明確函數只有一個唯一的輸入值n ，第二找到遞歸結束條件或者遞歸邊界，可以發現當臺階是1或者2時候最容易得到，至于遞推式，可以發現青蛙在每次跳的時候有兩種跳法，那青蛙怎么到達第n 個臺階，就是有兩種跳法，分別對應f(n-1) 和 f(n-2) ，所以遞歸式就是f(n)=f(n-1)+f(n-2) ,那么整個算法就是如下：
//一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
//1。定義函數
public int f2(int n) {
//2.確定邊界
if (n == 1)
return 1;
if (n == 2)
return 2;
//3.確定遞歸式
return f2(n-1) + f2(n-2);
}繼續檢查邊界，發現n如果小于1，就會陷入死循環，那么程序可以改成這樣：
if (n == 1) return 1; if (n == 2) return 2; if (n < 1) return 0; //當然簡單寫，可以這樣搞 if (n < 1) return 0; if (n <= 2) return n;
單鏈表的反轉，一般考慮到是雙指針反轉，當然遞歸寫也可以，同樣，首先定義函數，發現函數只有一個入參即節點node 這個node 在根節點或者任意中間節點都適用，其二確定邊界，在反轉單鏈表時候，可能會漏了node.next 的邊界，此時兩種方式，1，冗余寫，只要你考慮到了，這可能是邊界，你多寫了絕對不會錯，甚至，你可以多寫兩到三步也完全沒問題，2，少寫的話，就寫完遞歸方式再來檢查，比如反轉單鏈表這個題，你會看到如果node.next 為空，那么node.next.next 就會報空指針問題，一般寫完遞歸式后最好回頭檢查一下邊界，可以查缺補漏，去冗余或者補條件。
此題的核心點是解開鏈的遞歸式，就是
Node last = f3(node.next); //假設當前節點的下一節點后的鏈表已經反轉 node.next.next = node; //當前節點指向的節點指向當前節點 node.next = null ;//原來當前節點是指向下一節點的，解開當前節點，并把節點指向空 //此處解釋，為什么指向空，首先可以將node節點理解為第一個節點，那么第一節點反轉后，就是最后一個節點，則指向是null，否則它還是指向2，就有問題喲 //那么如果不是第一個節點呢？這個指針是怎么指向的
舉個例子，假設，單鏈表是1，2，3，4，5那么遞歸的過程如下圖:
看圖，可以發現每一步的當前節點，放入反轉鏈表后，都是最后一個，那它必然指向null 這樣懂了把！
class Node{
int data;
Node next;
}
public Node f3(Node node) {
//2.確定返回邊界
if (node == null || node.next == null)
return node;
//3.拿到遞歸推導
Node last = f3(node.next);
node.next.next = node;
node.next = null ;//這個的作用是什么?,解開死循環，最后是有A->B,B->A
return last;
}遞歸遍歷樹也是最簡單的，假設你之前沒有看過遍歷的代碼，那么從零來開始考慮這個問題，首先定義函數，確認入參和單鏈表反轉類似，只需要一個TreeNode 節點，然后考慮邊界為null ，和不為null ，你首先想到是不是這樣？
if (node == null)
return ;
if (node.left == null && node.right == null) {
System.out.pritln(node.val);
return ;
}現在看起來是有點冗余，但是假設你并不知道，那么接下來下遞歸式，以先序為例
//首先節點本身 System.out.println(node.val); //然后節點左 preOrder(node.left); //然后節點右 preOrder(node.right);
就這樣完了，然后回顧前面的邊界問題，只有上面的代碼兩行，可以看到在節點為null 的時候，就直接return 了，不用考慮子節點，字節點的邊界在父節點的邊界中已經考慮到了，當然寫了這條邊界完全不影響程序運行哦，所以最終的前中后序遍歷如下代碼：
//二叉樹前序遍歷
public static void preOrder(TreeNode node) {
if (node == null)
return;
System.out.println(node.val);
preOrder(node.left);
preOrder(node.right);
}
//二叉樹中序遍歷
public static void inOrder(TreeNode node) {
if (node == null)
return;
preOrder(node.left);
System.out.println(node.val);
preOrder(node.right);
}
//二叉樹后序遍歷
public static void postOrder(TreeNode node) {
if (node == null)
return;
preOrder(node.left);
preOrder(node.right);
System.out.println(node.val);
}下面，我們補一個遞歸算法題，輸入一個二叉樹序列，來還原構造二叉樹，順便測試一下前面的遍歷樹的代碼，同樣熟悉了遞歸的套路后，我們直接來寫代碼
//1.定義函數確認，只需要一個參數，即剩余序列
public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
//定義一個空的樹節點，此處為了整齊劃一，在邊界和遞歸體里面都可以用，所以寫在第一行
TreeNode node = null;
//2.邊界
if (inputList == null || inputList.isEmpty())
return node;
//3.主要遞歸體，從鏈表中刪除并取第一個元素，構建好左右節點，最后返回當前節點
Integer data = inputList.removeFirst();
//data，主要是異常值判斷，前面已經判斷過鏈表為空了
if (data != null) {
node = new TreeNode(data);
node.left = createBinaryTree(inputList);
node.right = createBinaryTree(inputList);
}
return node;
}
public static void main(String[] args) {
//前序遍歷序列
LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4}));
TreeNode node = createBinaryTree(inputList);
//前序遍歷
System.out.println("前序遍歷：");
preOrder(node);
}到此，相信大家對“怎么寫好java遞歸函數”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
