遞歸原理

---

遞歸是一種解決問題的有效方法，在遞歸過程中，函數將自身作為子例程調用

你可能想知道如何實現調用自身的函數。訣竅在于，每當遞歸函數調用自身時，它都會將給定的問題拆解為子問題。

遞歸調用繼續進行，直到到子問題無需進一步遞歸就可以解決的地步。

為了確保遞歸函數不會導致無限循環，它應具有以下屬性：

一個簡單的基本案例（basic case）（或一些案例） ——?能夠不使用遞歸來產生答案的終止方案。---終止條件

一組規則，也稱作遞推關系（recurrence relation），可將所有其他情況拆分到基本案例。 ? ? ? ?? ---遞推關系

注意，函數可能會有多個位置進行自我調用。

?

示例

---

讓我們從一個簡單的編程問題開始：

以相反的順序打印字符串。

你可以使用迭代的辦法輕而易舉地解決這個問題，即從字符串的最后一個字符開始遍歷字符串。但是如何遞歸地解決它呢？

首先，我們可以將所需的函數定義為?printReverse(str[0...n-1])，其中?str[0]?表示字符串中的第一個字符。然后我們可以分兩步完成給定的任務：

printReverse(str[1...n-1])：以相反的順序打印子字符串?str[1...n-1]?。

print(str[0])：打印字符串中的第一個字符。

請注意，我們在第一步中調用函數本身，根據定義，它使函數遞歸。

例子：

private static void printReverse(char [] str) {helper(0, str); }private static void helper(int index, char [] str) {if (str == null || index >= str.length) {return;}// 這可以理解為，先輸出當前index之后索引的字符（即index+1），且該方法可以宏觀理解為，已經輸出后后邊所有的字符了，接下來輸出當前字符 helper(index + 1, str);System.out.print(str[index]); }

?

遞歸例子：

一、反轉字符串

問題：

編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 char[] 的形式給出。 不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。 你可以假設數組中的所有字符都是 ASCII 碼表中的可打印字符。 package com.example.demo;public class TestString0001 {public void reverseString(char[] s) {int len = s.length;swap(s, 0, len - 1);}private void swap(char[] s, int left, int right) {if (left > right) {return;}char temp = s[left];s[left] = s[right];s[right] = temp;swap(s, left+1, right-1);}public static void main(String[] args) {TestString0001 t = new TestString0001();char[] arr = {'H', 'a', 'n', 'n', 'a', 'h'};t.reverseString(arr);for (char c : arr) {System.out.println(c);}} }

?

二、問題

兩兩交換鏈表中的節點給定一個鏈表，兩兩交換其中相鄰的節點，并返回交換后的鏈表。 你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。 class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}ListNode temp = head;head = head.next;temp.next = head.next;head.next = temp;//下一個交換head.next.next = swapPairs(head.next.next);return head;} }

?

?

?

?

相關：leetcode有關遞歸：

https://leetcode-cn.com/explore/featured/card/recursion-i/256/principle-of-recursion/1101/

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的基础-递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。