[TOC]
# 簡介
本質上,將原來的問題,轉化為更小的同一問題
舉例
`Sum(arr[0...n-1]) = arr[0] + Sum(arr[1...n-1])`更小的同一問題
`Sum(arr[1...n-1]) = arr[1] + Sum(arr[2...n-1])`更小的問題
`Sum(arr[n-1...n-1]) = arr[n-1] + Sum([])` 最基本的問題
# 代碼
~~~
public class Sum {
public static int sum(int[] arr) {
return sum(arr, 0);
}
//計算arr[l...n)這個區間內所有數字的和
private static int sum(int[] arr, int l) {
//當初始值和我們這個數組的長度相等的時候,表示已經到了邊界了
if (l == arr.length) {
return 0;
}
return arr[l] + sum(arr, l + 1);
}
//測試下
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6};
System.out.println(sum(nums));
}
}
~~~
# 分析
1. 有求解的最基本問題,需要我們自己寫
2. 把原問題轉化為更小的問題(核心)
注意遞歸函數的宏觀語義
遞歸函數就是一個函數,完成一個功能
# 鏈表天然的遞歸性
## 問題
摘取leetcode
https://leetcode-cn.com/problems/remove-linked-list-elements/description/
刪除鏈表中等于給定值 val 的所有元素。
示例
給定: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
返回: 1 --> 2 --> 3 --> 4 --> 5
我們再看下leetcode的這個問題
## 代碼
~~~
public class Solution {
public ListNode removeElements(ListNode head, int val) {
//當遞歸到頭節點為null,表示鏈表已經被查完了
if (head == null) {
return null;
}
// ListNode res = removeElements(head.next, val);
// //head也滿足被刪除的條件
// if (head.val == val) {
// //表示head后面的元素滿足條件
// return res;
// } else {
// //這邊表示head不要刪除
// head.next = res;
// //就把head那邊滿足條件的返回
// return head;
// }
//簡寫
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}
~~~
## 分析
## 總結
遞歸調用是有代價的:函數調用+系統棧空間
