1. 什么是遞歸？

遞歸是指在函數的定義中使用函數自身的過程。簡單來說，遞歸是通過將大問題分解為更小的子問題來解決問題的一種方法。遞歸函數在執行時會反復調用自身，直到達到某個終止條件。

2. 遞歸解決什么問題？

遞歸的使用可以簡化問題的解決過程，特別適用于那些具有遞歸結構或可分解為子問題的復雜問題。遞歸的主要優勢在于它提供了一種自然而簡潔的方式來解決這些問題。

3. 遞歸的步驟

1. 定義遞歸函數的基本情況（終止條件）：遞歸函數需要定義一個或多個基本情況，即當滿足某個條件時，遞歸停止并返回結果。這是確保遞歸函數不會無限循環的關鍵。
2. 將大問題分解為子問題：遞歸函數應該通過將大問題分解為一個或多個更小的子問題來解決。每個子問題都是原始問題的規模更小的版本。
3. 在遞歸函數中調用自身：在解決子問題時，遞歸函數會調用自身來處理子問題。遞歸函數的調用應該是在滿足遞歸終止條件之前的步驟。
4. 組合子問題的結果：遞歸函數在處理完子問題后，需要將子問題的結果組合起來得到原始問題的解。

4. 使用遞歸的注意事項

1. 確保遞歸終止條件的正確性：遞歸函數必須定義一個或多個終止條件，以避免無限遞歸。如果終止條件不正確或者缺失，遞歸函數可能會導致無限循環，最終耗盡計算資源。
2. 確保每次遞歸調用都能向終止條件靠近：遞歸調用的參數或輸入應該是可以縮小問題規模的，這樣每次遞歸調用都能使問題向終止條件靠近。否則，遞歸函數可能會陷入無盡的遞歸循環。
3. 注意遞歸的性能問題：遞歸函數可能會生成大量的函數調用和堆棧幀，消耗較多的內存和計算資源。在某些情況下，使用迭代等其他方法可能更高效。

5. 示例

1. 合并兩個有序鏈表

   public class MergeSortedLists {public ListNode mergeLists(ListNode l1, ListNode l2) {// 處理遞歸終止條件if (l1 == null) {return l2;}if (l2 == null) {return l1;}// 比較兩個鏈表頭節點的值，并選擇較小的節點作為合并后鏈表的頭節點if (l1.val < l2.val) {l1.next = mergeLists(l1.next, l2); // 遞歸調用mergeLists函數return l1;} else {l2.next = mergeLists(l1, l2.next); // 遞歸調用mergeLists函數return l2;}}
   }
   

   定義一個遞歸函數mergeLists，該函數接受兩個有序鏈表的頭節點作為參數，并返回合并后的鏈表的頭節點。

   在函數內部，首先處理遞歸終止條件。如果其中一個鏈表為空，直接返回另一個鏈表的頭節點。

   比較兩個鏈表的頭節點的值，將較小值的節點作為合并后鏈表的頭節點，并將其next指針指向遞歸調用mergeLists函數的結果。

   遞歸調用mergeLists函數，傳入較小節點的next指針和另一個鏈表的頭節點作為參數。

   返回合并后的鏈表的頭節點。

2. 判斷鏈表是否有環

   public class Solution {public boolean hasCycle(ListNode head) {// 判斷鏈表是否為空或只有一個節點，不構成環if (head == null || head.next == null) {return false;}ListNode slow = head;  // 慢指針ListNode fast = head.next;  // 快指針return hasCycleRecursive(slow, fast);}private boolean hasCycleRecursive(ListNode slow, ListNode fast) {// 如果快指針到達鏈表末尾，說明沒有環if (fast == null || fast.next == null) {return false;}// 如果快指針追上慢指針，說明存在環if (fast == slow || fast.next == slow) {return true;}// 繼續移動指針return hasCycleRecursive(slow.next, fast.next.next);}
   }
   

   首先，在 hasCycle() 方法中檢查鏈表是否為空或只有一個節點，這種情況下不會形成環，直接返回 false。

   然后，將慢指針 slow 初始化為鏈表頭，快指針 fast 初始化為 slow 的下一個節點。

   接下來，調用 hasCycleRecursive() 方法進行遞歸判斷。在遞歸方法中，首先判斷快指針是否到達鏈表末尾，如果是，則鏈表不包含環，返回 false。然后，判斷快指針是否追上慢指針或者快指針的下一個節點是否追上慢指針，如果是，則鏈表包含環，返回 true。最后，繼續遞歸調用 hasCycleRecursive() 方法，將慢指針指向下一個節點，快指針指向下下個節點，繼續進行判斷。

   注意，這里使用了兩個條件進行判斷，即快指針是否追上慢指針，或者快指針的下一個節點是否追上慢指針。這是因為快指針每次移動兩步，而慢指針每次移動一步，所以在形成環的情況下，兩個指針可能會有一個節點的差距。

   最后，在主函數中調用 hasCycle() 方法，傳入鏈表的頭節點，即可判斷鏈表是否存在環。