本篇內(nèi)容主要講解“怎么寫好java遞歸函數(shù)”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“怎么寫好java遞歸函數(shù)”吧!
為臨猗等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及臨猗網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、臨猗網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！
寫遞歸，就是寫三要素的實(shí)現(xiàn)，三要素分別為函數(shù)，邊界，遞推公式，剛開始只要記住要這么寫，寫幾個(gè)算法之后，就能慢慢明白為什么要這樣搞。
明確你的函數(shù)是干什么用的，函數(shù)的入?yún)?yīng)該是什么，返回值是什么，這三個(gè)問題，先從函數(shù)是干什么用的開始，你可以定義一個(gè)函數(shù)f() 假設(shè)已經(jīng)實(shí)現(xiàn)了每一步遞歸的實(shí)現(xiàn)，再去明確這個(gè)實(shí)現(xiàn) 到底做了什么，入?yún)⒅辽僖裁?，返回值和參?shù)返回可以理解為是一個(gè)東西，都是為了返回給上層調(diào)用或者全局的一個(gè)數(shù)據(jù)，想清楚函數(shù)的三個(gè)要素，那你的函數(shù)就定義好了。
同樣，先這樣去做，再去想為什么，這一步要判斷的就是函數(shù)的入?yún)?，入?yún)⒌?code>null ，入?yún)槌跏贾?，比如斐波那契?shù)列的前1位或者2位，開始時(shí)候可能不一定想的完全，那沒關(guān)系，下面的一步還會(huì)繼續(xù)完善，所以我這里舉得例子是斐波那契的前1或2位，而不是直接說結(jié)論，這一步驟是在函數(shù)的實(shí)現(xiàn)里面，所以考慮方式就是假設(shè)，入?yún)⒌搅伺R界值或者初始值，或者特殊值，你要判斷一下，第一遍寫的時(shí)候比如斐波那契，可以直接這么寫
if (n == 1) return 1; if (n == 2) return 1;
想到的不一定完全對(duì)，或者那么地很優(yōu)雅， 沒關(guān)系，只要想到要考慮邊界就可以了。下面就是想邊界的意義是什么？有兩點(diǎn)，其一，異常值邊界，其二遞歸結(jié)束判斷，比如此題中的n < 0 怎么辦，和 n == 1 和 n == 2 就分別對(duì)應(yīng)前面說的，當(dāng)然這兩點(diǎn)可能考慮不那么完全，假設(shè)你只考慮了像前面代碼中的，或者寫邊界時(shí)候發(fā)現(xiàn)寫的多了，或者冗余了，這樣不影響程序的結(jié)果，那么寫完遞推公式，我們?cè)賮砘仡欉吔鐔栴}。
這個(gè)就要先談意義，再談實(shí)現(xiàn)了，意義在于逐漸減少算法的規(guī)模，或者定義一種方式讓輸入的值盡可能地靠近臨界值，也就是找一個(gè)關(guān)系f(n) 與 f(n-x)序列的關(guān)系，f(n) 代表要解決的問題規(guī)模，f(n-x) 比n小的問題規(guī)模的函數(shù)值，這是遞歸函數(shù)中的關(guān)鍵一步，沒有遞推公式，就沒有遞歸。例如斐波那契序列，中的遞推公式是f(n)=f(n-1) + f(n-2)我們來觀察這個(gè)公式，發(fā)現(xiàn)其第n 于 n-1 和 n-2 有關(guān)系，所以我們來看，如果輸入任何整數(shù)，那么n-1,n-2 可能取值是負(fù)數(shù)，0，1+，可以看到邊界0和負(fù)數(shù)沒有考慮在內(nèi)，所以，這時(shí)回顧前面1.2 的遞歸，我們來補(bǔ)充一下邊界后得到：
if (n <= 2) return 1;
下面通過三個(gè)簡(jiǎn)單例子，我們來練習(xí)使用遞歸，分別是青蛙跳臺(tái)階問題，等同于斐波那契序列，遞歸方式反轉(zhuǎn)單鏈表，遞歸遍歷樹，以及針對(duì)三個(gè)
第一定義函數(shù),明確函數(shù)只有一個(gè)唯一的輸入值n ，第二找到遞歸結(jié)束條件或者遞歸邊界，可以發(fā)現(xiàn)當(dāng)臺(tái)階是1或者2時(shí)候最容易得到，至于遞推式，可以發(fā)現(xiàn)青蛙在每次跳的時(shí)候有兩種跳法，那青蛙怎么到達(dá)第n 個(gè)臺(tái)階，就是有兩種跳法，分別對(duì)應(yīng)f(n-1) 和 f(n-2) ，所以遞歸式就是f(n)=f(n-1)+f(n-2) ,那么整個(gè)算法就是如下：
重慶分公司
重慶分公司
//一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
//1。定義函數(shù)
public int f2(int n) {
//2.確定邊界
if (n == 1)
return 1;
if (n == 2)
return 2;
//3.確定遞歸式
return f2(n-1) + f2(n-2);
}繼續(xù)檢查邊界，發(fā)現(xiàn)n如果小于1，就會(huì)陷入死循環(huán)，那么程序可以改成這樣：
if (n == 1) return 1; if (n == 2) return 2; if (n < 1) return 0; //當(dāng)然簡(jiǎn)單寫，可以這樣搞 if (n < 1) return 0; if (n <= 2) return n;
單鏈表的反轉(zhuǎn)，一般考慮到是雙指針反轉(zhuǎn)，當(dāng)然遞歸寫也可以，同樣，首先定義函數(shù)，發(fā)現(xiàn)函數(shù)只有一個(gè)入?yún)⒓垂?jié)點(diǎn)node 這個(gè)node 在根節(jié)點(diǎn)或者任意中間節(jié)點(diǎn)都適用，其二確定邊界，在反轉(zhuǎn)單鏈表時(shí)候，可能會(huì)漏了node.next 的邊界，此時(shí)兩種方式，1，冗余寫，只要你考慮到了，這可能是邊界，你多寫了絕對(duì)不會(huì)錯(cuò)，甚至，你可以多寫兩到三步也完全沒問題，2，少寫的話，就寫完遞歸方式再來檢查，比如反轉(zhuǎn)單鏈表這個(gè)題，你會(huì)看到如果node.next 為空，那么node.next.next 就會(huì)報(bào)空指針問題，一般寫完遞歸式后最好回頭檢查一下邊界，可以查缺補(bǔ)漏，去冗余或者補(bǔ)條件。
此題的核心點(diǎn)是解開鏈的遞歸式，就是
Node last = f3(node.next); //假設(shè)當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)后的鏈表已經(jīng)反轉(zhuǎn) node.next.next = node; //當(dāng)前節(jié)點(diǎn)指向的節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn) node.next = null ;//原來當(dāng)前節(jié)點(diǎn)是指向下一節(jié)點(diǎn)的，解開當(dāng)前節(jié)點(diǎn)，并把節(jié)點(diǎn)指向空 //此處解釋，為什么指向空，首先可以將node節(jié)點(diǎn)理解為第一個(gè)節(jié)點(diǎn)，那么第一節(jié)點(diǎn)反轉(zhuǎn)后，就是最后一個(gè)節(jié)點(diǎn)，則指向是null，否則它還是指向2，就有問題喲 //那么如果不是第一個(gè)節(jié)點(diǎn)呢？這個(gè)指針是怎么指向的
舉個(gè)例子，假設(shè)，單鏈表是1，2，3，4，5那么遞歸的過程如下圖:
看圖，可以發(fā)現(xiàn)每一步的當(dāng)前節(jié)點(diǎn)，放入反轉(zhuǎn)鏈表后，都是最后一個(gè)，那它必然指向null 這樣懂了把！
class Node{
int data;
Node next;
}
public Node f3(Node node) {
//2.確定返回邊界
if (node == null || node.next == null)
return node;
//3.拿到遞歸推導(dǎo)
Node last = f3(node.next);
node.next.next = node;
node.next = null ;//這個(gè)的作用是什么?,解開死循環(huán)，最后是有A->B,B->A
return last;
}遞歸遍歷樹也是最簡(jiǎn)單的，假設(shè)你之前沒有看過遍歷的代碼，那么從零來開始考慮這個(gè)問題，首先定義函數(shù)，確認(rèn)入?yún)⒑蛦捂湵矸崔D(zhuǎn)類似，只需要一個(gè)TreeNode 節(jié)點(diǎn)，然后考慮邊界為null ，和不為null ，你首先想到是不是這樣？
if (node == null)
return ;
if (node.left == null && node.right == null) {
System.out.pritln(node.val);
return ;
}現(xiàn)在看起來是有點(diǎn)冗余，但是假設(shè)你并不知道，那么接下來下遞歸式，以先序?yàn)槔?/p>
//首先節(jié)點(diǎn)本身 System.out.println(node.val); //然后節(jié)點(diǎn)左 preOrder(node.left); //然后節(jié)點(diǎn)右 preOrder(node.right);
就這樣完了，然后回顧前面的邊界問題，只有上面的代碼兩行，可以看到在節(jié)點(diǎn)為null 的時(shí)候，就直接return 了，不用考慮子節(jié)點(diǎn)，字節(jié)點(diǎn)的邊界在父節(jié)點(diǎn)的邊界中已經(jīng)考慮到了，當(dāng)然寫了這條邊界完全不影響程序運(yùn)行哦，所以最終的前中后序遍歷如下代碼：
//二叉樹前序遍歷
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);
}下面，我們補(bǔ)一個(gè)遞歸算法題，輸入一個(gè)二叉樹序列，來還原構(gòu)造二叉樹，順便測(cè)試一下前面的遍歷樹的代碼，同樣熟悉了遞歸的套路后，我們直接來寫代碼
//1.定義函數(shù)確認(rèn)，只需要一個(gè)參數(shù)，即剩余序列 public static TreeNode createBinaryTree(LinkedListinputList) { //定義一個(gè)空的樹節(jié)點(diǎn)，此處為了整齊劃一，在邊界和遞歸體里面都可以用，所以寫在第一行 TreeNode node = null; //2.邊界 if (inputList == null || inputList.isEmpty()) return node; //3.主要遞歸體，從鏈表中刪除并取第一個(gè)元素，構(gòu)建好左右節(jié)點(diǎn)，最后返回當(dāng)前節(jié)點(diǎn) Integer data = inputList.removeFirst(); //data，主要是異常值判斷，前面已經(jīng)判斷過鏈表為空了 if (data != null) { node = new TreeNode(data); node.left = createBinaryTree(inputList); node.right = createBinaryTree(inputList); } return node; } public static void main(String[] args) { //前序遍歷序列 LinkedList inputList = new LinkedList (Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4})); TreeNode node = createBinaryTree(inputList); //前序遍歷 System.out.println("前序遍歷："); preOrder(node); }
到此，相信大家對(duì)“怎么寫好java遞歸函數(shù)”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！
