遞迴-1

簡介1

函數呼叫自身的過程稱為遞歸，
對應的函數稱為遞歸函數.
由於電腦程式設計是數學的基本應用，所以讓
我們首先嘗試理解遞歸背後的數學推理。
一般來說，我們都知道函數的概念。簡而言之，函數是
提供輸入時產生輸出的數學方程式。例如：
假設函數 F(x) 是由下式定義的函數： F(x) = x^2 + 4
我們可以將此函數的 Java 程式碼編寫為：

public static int F(int x){
返回 (x * x + 4);
}

現在，我們可以將不同的 x 值傳遞給該函數並接收我們的輸出
相應地。
在繼續遞歸之前，讓我們試著理解另一個數學
概念稱為數學歸納法原理 (PMI)。

數學歸納原理（PMI）是一種證明陳述的技術，
公式，或關於一組自然數的定理。它有
以下三個步驟：
1.** 小案例的步驟*：在這一步驟中，我們將證明
所需的陳述 基本情況，例如 n = 0 或 n = 1。
2.* 假設步驟**：在這一步驟中，我們將假設所需的語句
對於 n = k 有效。

1. 證明步驟：根據假設步驟的結果，我們將證明， 只要 n = k 為真，n = k + 1 對所需方程式也成立。

例如：讓我們用數學歸納法證明：
S(N): 1 + 2 + 3 + ... + N = (N * (N + 1))/2
(前N個自然數和)
證明：
步驟 1：對於 N = 1，S(1) = 1 為真。
步驟 2：假設，對於 N = k，給定的陳述成立，即
1 + 2 + 3 + .... + k = (k * (k + 1))/2
步驟 3：讓我們使用步驟 2 來證明 N = k + 1 的命題。

證明：1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
證明：

將第 2 步驟所得的結果中的 LHS 和 RHS 加入 (k+1)：
1 + 2 + 3 + ... + (k+1) = (k*(k+1))/2 + (k+1)

現在，從 RHS 端取 (k+1) 個公用：
1 + 2 + 3 + ... + (k+1) = (k+1)*((k + 2)/2)

根據我們試圖證明的陳述：
1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
由此證明。

遞歸的工作

總結以上三點，我們就可以定義遞歸方法的步驟
步驟：
●基本情況：遞迴函數必須有終止條件，在該條件下
該進程將停止呼叫自身。這種情況稱為基本情況。如果沒有基本情況，它會不斷調用自己並陷入
無限循環。很快，就會超出遞歸深度*並拋出
錯誤。
●遞歸呼叫：遞歸函數將在較小的版本上呼叫自身
的主要問題。我們在編寫此步驟時需要小心
對於正確找出你的小問題是什麼至關重要。
●小計算：一般我們在每個遞迴中執行一次計算步驟
稱呼。我們可以在遞歸呼叫之前或之後實現這個​​計算步驟
取決於問題的性質。

注意：遞歸使用儲存遞歸呼叫的內建堆疊。因此，
遞歸呼叫的次數必須盡可能少，以避免記憶體溢位。如果
遞歸呼叫次數超過最大允許數量，
**將超過遞歸深度**。
現在，讓我們看看如何使用遞歸解決一些常見問題

問題陳述 - 求一個數的階乘

方法：找出 PMI 的三個步驟，然後使用
將其關聯起來 遞歸

1. 歸納步驟：計算數字 n - F(n) 的階乘 歸納假設：我們已經得到了 n-1 - F(n-1)
的階乘
2. 以 F(n-1) 表示 F(n)：F(n)=n*F(n-1)。因此我們得到

public static int fact(int n){
int ans = 事實(n-1); #假設步驟
返回 ans * n; #從假設步驟解決問題
}

1. 程式碼尚未完成。缺少的部分是基本情況。現在我們將 試運轉以查找需要停止遞歸的情況。考慮 n = 5：

正如我們在上面看到的，我們已經知道 n = 0 的答案，即 1。所以我們將
將此作為我們的基本情況。因此，程式碼現在變成：

公用靜態 int 階乘(int n){
if (n == 0) // 基本情況
回傳 1;
其他
傳回 n*階乘(n-1); // 遞迴情況
}

以上是遞迴-1的詳細內容。更多資訊請關注PHP中文網其他相關文章！