遞迴函式

---

簡介

遞迴函式是一種在編碼中使用的獨特函式型別。它被定義為一個使用自身來執行其他項的函式。此函式通常用於確定階乘數、迴文數、數字的冪等。在本教程中，我們將學習遞迴函式的基本定義、遞迴定義的函式、算術和幾何序列的公式以及一些已解決的示例。

遞迴定義

遞迴的意思是重複或自我呼叫。在計算機科學中，遞迴發生在一個函式重複自身時。遞迴函式定義為一個程式碼，它自身被用來計算序列的連續項。換句話說，在執行過程中呼叫自身的函式被稱為遞迴函式。遞迴函式也用於簡化複雜問題。讓我們考慮一個現實生活中的例子來理解遞迴函式的定義。假設 Ram 有 12000 盧比現金。他想數它。但是，他獨自數錢相當困難。因此，他讓 Gopal 和 Hari 幫忙數錢。他們將錢隨機分成三部分並開始計數。當他們完成計數後，Ram 將所有錢加起來，總和為 1200 盧比。如果 Ram 單獨計數，總金額將是精確的。在編碼中，這被稱為遞迴。遞迴具有以下優點：

• 複雜的問題可以分解成更簡單的任務。

• 遞迴透過縮短編碼長度來節省時間和精力。

遞迴定義的函式

每個遞迴定義的函式都有兩個組成部分。一個是序列的第一項（即最小值），記為 𝑓(0) 或 𝑓(1)。第二個是確定序列連續項的表示式，記為 𝑓(𝑝)。

我們將透過一個例子來理解這一點。讓我們考慮一個序列 2、4、6、8 和 10。

在上面的例子中，序列的第一項 $\mathrm{=\:f(1)\:=\:2}$

確定序列連續項的表示式可以寫成

$$\mathrm{f(n)\:=\:f(n\:-\:1)\:+\:2}$$

現在我們可以使用上面的表示式來計算序列的連續項，如下所示：

$$\mathrm{f(2)\:=\:f(1)\:+\:2\:=\:2\:+\:2\:=\:4}$$

$$\mathrm{f(3)\:=\:f(2)\:+\:2\:=\:4\:+\:2\:=\:6}$$

$$\mathrm{f(4)\:=\:f(3)\:+\:2\:=\:6\:+\:2\:=\:8}$$

$$\mathrm{f(5)\:=\:f(4)\:+\:2\:=\:8\:+\:2\:=\:10}$$

是什麼使函式成為遞迴函式？

如果需要前一項才能找到序列，則稱該函式為遞迴函式。這意味著我們需要 $\mathrm{(n\:-\:1)^{th}}$ 和 $\mathrm{(n\:-\:2)^{th}}$ 項來找到序列的 $\mathrm{n^{th}}$ 項。前一項對於確定給定序列是否為遞迴序列是必要的。通常，遞迴函式中會提供第一項以及序列項之間的相關性。

公式

假設一個序列由 𝑝1、𝑝2、𝑝3、𝑝4、……、𝑝𝑛 給出，遵循遞迴表示式。確定序列的 $\mathrm{n^{th}}$ 項的遞迴公式可以透過以下方式獲得：

$$\mathrm{P_{n}\:=\:P_{n\:-\:1}\:+\:P_{1}}$$

上述公式也稱為算術序列的遞迴公式。此外，幾何序列的公式如下：

$$\mathrm{p_{n}\:=\:r\times\:p_{n\:-\:1}\:(其中\:r\:是公比)}$$

算術序列的遞迴公式

應該遵循以下步驟來推導算術序列的公式。

• 步驟 1 - 檢查序列是否為算術序列。這可以透過確定兩個連續項之間的差值來驗證。如果減法值保持不變，則該序列可以稱為算術序列。

• 步驟 2 - 計算序列的公差，並將其記為 h。

• 步驟 3 - 使用公差在 $\mathrm{n^{th}}$ 項與其前一項（即 $\mathrm{(n\:-\:1^{th}}$）之間建立關聯。因此，算術序列的遞迴公式可以表示為 $\mathrm{p_{n}\:=\:p_{n\:-\:1}\:+\:h}$

幾何序列的遞迴公式

應該遵循以下步驟來推導算術序列的公式

• 步驟 1：檢查序列是否為幾何序列。這可以透過計算兩個連續項之間的比率來驗證。如果比率值保持不變，則該序列可以稱為幾何序列。

• 步驟 2：計算序列的公比，並將其記為 r。

• 步驟 3：使用公比在 $\mathrm{n^{th}}$ 項與其前一項（即 $\mathrm{(n\:-\:1^{th}}$）之間建立關聯。因此，幾何序列的遞迴公式可以表示為 $\mathrm{p_{n}\:=\:r\times\:p_{n\:-\:1}}$。

已解決的問題

1) 給出如下序列：

$$\mathrm{-\frac{1}{2}\:,\:-\frac{1}{6}\:,\:\frac{1}{6}\:.\:\frac{1}{2}\:,\:\frac{5}{6}\:,\:\frac{7}{6}\:........}$$

計算上述序列的序列公式。

答案 −

第一步，我們必須檢查序列是算術序列還是幾何序列。

對於算術序列，存在公差。

因此，$\mathrm{-\frac{1}{6}\:-\:(\frac{1}{2})\:=\:\frac{1}{3}}$

$$\mathrm{\frac{1}{6}\:-\:(-\frac{1}{6})\:=\:\frac{1}{3}}$$

$$\mathrm{\frac{1}{2}\:-\:(-\frac{1}{6})\:=\:\frac{1}{3}}$$

$$\mathrm{\frac{5}{6}\:-\:(\frac{1}{2})\:=\:\frac{1}{3}}$$

因此，已驗證給定序列是算術序列。

序列的公差 $\mathrm{=\:h\:=\:\frac{1}{3}}$

∴給定函式的遞迴公式為 $\mathrm{p_{n}\:=\:p_{n\:-\:1}\:+\:\frac{1}{3}}$

2)確定算術序列 $\mathrm{p_{n}\:=\:p_{n\:-\:1}\:-\:7}$ 的前 4 項。序列的第一項為 $\mathrm{p_{1}\:=\:3}$。

答案 −

給出：

序列的第一項為 $\mathrm{p_{1}\:=\:3}$

現在，使用遞迴公式

$$\mathrm{p_{2}\:=\:p_{1}\:-\:7\:=\:3\:-\:7\:=\:-4}$$

$$\mathrm{p_{3}\:=\:p_{2}\:-\:7\:=\:-4\:-\:7\:=\:-11}$$

$$\mathrm{p_{4}\:=\:p_{3}\:-\:7\:=\:-11\:-\:7\:=\:-18}$$

4) 給出如下序列：

$$\mathrm{\frac{1}{2}\:,\:\frac{1}{3}\:,\frac{2}{9}\:,\:\frac{4}{27}\:,\:\frac{8}{81}\:,\:.......}$$

計算上述序列的序列公式。另外，求序列的第 6 項。

答案 −

第一步，我們必須檢查序列是算術序列還是幾何序列。

對於幾何序列，存在公比。

$$\mathrm{\frac{\frac{1}{3}}{\frac{1}{2}}\:=\:\frac{\frac{2}{9}}{\frac{1}{3}}\:=\:\frac{\frac{4}{27}}{\frac{2}{9}}\:=\:\frac{2}{3}}$$

因此，已驗證給定序列是幾何序列。

序列的公比 $\mathrm{=\:r\:=\:\frac{2}{3}}$

∴給定函式的遞迴公式為 $\mathrm{p_{n}\:=\:\frac{2}{3}\times\:p_{n\:-\:1}}$

∴序列的第 6 項為 $\mathrm{p_{6}\:=\:\frac{2}{3}\times\:p_{5}\:=\:\frac{2}{3}\times\:\frac{8}{81}\:=\:\frac{16}{243}}$

要點

• 遞迴函式總是重複自身以獲得序列的其他項。

• 有必要檢查序列是算術序列還是幾何序列

• 在算術序列中，存在公差，而在幾何序列中存在公比。

結論

本教程簡要介紹了遞迴函式。本教程簡要描述了遞迴函式的定義以及一個示例。此外，本教程還推導了算術和幾何序列的遞迴公式。此外，還提供了一些已解決的示例，以更好地理解此概念。總之，本教程可能有助於理解遞迴函式的基本概念。

常見問題

1. 遞迴函式的基本屬性是什麼？

遞迴函式具有三個基本屬性，例如：

• 它自身呼叫。

• 它必須有一個基本情況。

• 它必須改變其狀態並朝著基本情況移動。

2. 遞迴函式中應該有多少項？

沒有這樣的限制。遞迴函式可以有有限或無限數量的項。

3. 遞迴和迭代有什麼區別？

遞迴是在執行過程中自身重複，而迭代是重複執行特定指令。

4. 任何函式都可以是遞迴函式嗎？

不可以。只有當函式呼叫自身時，才能稱其為遞迴函式。

5. 遞迴函式的缺點是什麼？

遞迴邏輯通常難以理解，並且在編碼過程中會佔用更多記憶體。