聽說 90 % 的程序員都會遞歸？
通過數(shù)組求和看遞歸的基本性質(zhì)
鏈表的天然遞歸性
01
通過數(shù)組求和看遞歸的基本性質(zhì)
// begin 表示從數(shù)組中哪個索引位置開始//?當(dāng)begin?==?arr.length表示數(shù)組中沒有剩余元素if (begin == arr.length) {return 0;}
二是要知道遞歸遞推公式，就數(shù)組求和這個問題來說，遞推公式是:
arr[begin] + sum(begin + 1, arr);有了終止條件和遞推公式，就可以寫出遞歸求解數(shù)組中所有元素和的代碼了，實現(xiàn)如下：
public int sum (int[] arr) {// 調(diào)用遞歸函數(shù)，初始從0開始return sum(0, arr);}// 遞歸函數(shù)private int sum(int begin, int[] arr) {// begin 表示從數(shù)組中哪個索引位置開始// 當(dāng)begin == arr.length表示數(shù)組中沒有剩余元素if (begin == arr.length) {return 0;}// 我只計算我拿到的數(shù)組中第一個元素的值// 和數(shù)組中剩余元素總和的和????return?arr[begin]?+?sum(begin?+?1,?arr);?//?遞歸調(diào)用}
這里我們在第7行sum(int begin, int[] arr)這個方法中調(diào)用了sum(int begin, int[] arr)方法它自己，即16行的sum(begin + 1, arr)，這一點可能會讓你覺得困惑。
我們可以這樣理解，方法sum(int begin, int[] arr)是計算數(shù)組中從索引begin開始所有元素的總和，而該方法的計算規(guī)則是我計算的是當(dāng)前數(shù)組起始位置begin所對應(yīng)的元素值和數(shù)組中剩余元素的總和的和。那么，我就需要有個方法可以告訴我數(shù)組中剩余元素的總和是多少。
這時，剛好有個方法fun(int begin, int[] arr)，只要我告訴它數(shù)組是什么樣的，以及從哪個索引位置開始計算，它就會告訴我數(shù)組中剩余元素的總和。只不過這個方法fun(int begin, int[] arr)所需的參數(shù)和我自己一樣而已。于是，在代碼中看起來就是方法sum(int begin, int[] arr)調(diào)用了它自己。
02
鏈表的天然遞歸性
接著我們看下如何用遞歸思想解答LeetCode中#203.移除鏈表元素這個問題。
題目描述：
刪除鏈表中等于給定值 val 的所有節(jié)點。?
示例:?
輸入:?1->2->6->3->4->5->6,?val?=?6?
輸出:?1->2->3->4->5
LeetCode
public ListNode removeElements(ListNode head, int val) {// 遞歸終止條件if (head == null) {return null;}// 調(diào)用方法removeElements將當(dāng)前結(jié)點之后的鏈表部分中的// 和val值相等的結(jié)點刪除ListNode result = removeElements(head.next, val);// 如果當(dāng)前結(jié)點head的值等于val則返回resultif (head.val == val) {return result;} else {// 如果當(dāng)前結(jié)點head的值不等于val則// 將result掛在當(dāng)前結(jié)點head之后返回head.next = result;return head;}}
推薦閱讀：
“華為天才少年”自制百大Up獎杯，網(wǎng)友：技術(shù)難度不高侮辱性極強
5T技術(shù)資源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，單片機，樹莓派，等等。在公眾號內(nèi)回復(fù)「1024」，即可免費獲取！！