程式設計概念：遞迴技術

遞迴 - 用自身定義子例程。

遞迴是計算機科學中的一個關鍵領域，它依賴於您能夠透過解決同一問題的越來越小的例項來解決問題。

一種稱為Droste 效應 的遞迴的可視形式。此影像中的女士拿著一個物體，該物體包含她拿著相同物體的較小影像，該物體又包含她拿著相同物體的更小影像，以此類推。

名稱中遞迴的一個例子是GNU 作業系統，您可能會問 GNU 代表什麼

GNU = GNU 不是Unix

等一下，他們用重新說明名稱來定義名稱！

GNU

GNU 不是 Unix

GNU 不是 Unix 不是 Unix

GNU 不是 Unix 不是 Unix 不是 Unix

GNU 不是 Unix 不是 Unix 不是 Unix 不是 Unix

無限地

幸運的是，對於我們來說，使用計算機程式碼，我們的遞迴應該趨向於結束，因為我們正在解決同一問題的越來越小的例項，我們應該趨向於結束。在 GNU 示例中，名稱始終保持相同的大小，但在以下示例中，有一個結束

示例：一個遞迴的故事 function revise(essay) { read(essay); get_feedback_on(essay); apply_changes_to(essay); revise(essay) unless essay.complete?; } 這是描述修改論文過程的虛擬碼，修改過程包括閱讀論文、獲取反饋、應用更改，然後修改略微更好的論文。你不斷這樣做，直到論文完成。

讓我們看看一些計算機科學示例

階乘示例

一個經典的計算機遞迴過程示例是用於計算階乘 的函式自然數

$n!=n\times (n-1)\times (n-2)\times ...\times 1$

例如

$3!=3\times 2\times 1=6\$

$5!=5\times 4\times 3\times 2\times 1=120\$

$10!=10\times 9\times 8\times 7\times 6\times 5!=3628800\$

您注意到我在最終解決方案中做了什麼嗎？我沒有寫 5 * 4 * 3 * 2 * 1，而是使用了 5!，它產生 了相同的結果。回顧一下我們為什麼使用遞迴的定義，我們似乎透過解決同一問題的較小例項來解決大問題，因此階乘非常適合遞迴

10! = 10 * 9!
9! = 9 * 8!
8! = 8 * 7!
7! = 7 * 6!
6! = 6 * 5!
5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1

正如我們所看到的，每個 n! 都是 n * (n-1)! 的乘積。總之

$\operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=1\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>1\\\end{cases}}$

虛擬碼 （遞迴）
function factorial is: input: integer n such that n >= 1 output: [n × (n-1) × (n-2) × … × 1] 1. if n is >= 1, return [ n × factorial(n-1) ] 2. otherwise, return 1 end factorial

現在讓我們看看如何編寫程式碼來解決這個問題

function factorial(ByVal n as integer)
  if n >= 1 then
    return n * factorial(n-1) 'recursive call
  else
    return 1
  end if
end function

sub main()
  console.writeline(factorial(10))
end sub

它看起來非常簡單和優雅。但是它是如何工作的呢？

遞迴如何計算 factorial(4) 的圖表

讓我們建立一個跟蹤表並看看發生了什麼。這個跟蹤表將不同於您以前建立的跟蹤表，因為我們將不得不使用一個堆疊。如果您還沒有閱讀過關於堆疊 的內容，您必須在繼續之前這樣做

函式呼叫	n	返回行
1	4

到目前為止一切都很好，直到我們到達第 3 行。現在我們該怎麼辦？我們很快就會有兩個 n 值，一個用於函式呼叫 1，另一個用於函式呼叫 2。使用跟蹤表作為堆疊（堆疊底部在頂部，堆疊頂部在底部），我們將儲存關於函式呼叫的所有資料，包括它的 n 值，並記下我們在完成 factorial(3) 後需要返回到的行。

函式呼叫	n	返回行
1	4	3
2	3

現在我們有了類似於以前的情況，讓我們儲存返回地址並轉到 factorial(2)

函式呼叫	n	返回行
1	4	3
2	3	3
3	2

現在我們有了類似於以前的情況，讓我們儲存返回地址並轉到 factorial(1)

函式呼叫	n	返回行	返回值
1	4	3
2	3	3
3	2	3
4	1		1

現在我們遇到了另一個問題，我們找到了 factorial(1) 的結束。我們接下來去哪一行？由於我們將跟蹤表視為堆疊，我們將從頂部彈出上一個值，並檢視我們儲存的最後一個函式呼叫，即函式呼叫 3，factorial(2)，我們甚至知道要返回到的行，即第 3 行

return 2 * factorial(1)

我們知道從上一個返回值看 factorial(1) = 1。因此 factorial(2) 返回 2 * 1 = 2

函式呼叫	n	返回行	返回值
1	4	3
2	3	3
3	2	3	2
4	1		1

我們再次從堆疊中彈出最後一個函式呼叫，留下函式呼叫 2，factorial(3) 和第 3 行。

return 3 * factorial(2)

我們知道從上一個返回值看 factorial(2) = 2。因此 factorial(3) 返回 3 * 2 = 6

函式呼叫	n	返回行	返回值
1	4	3
2	3	3	6
3	2	3	2
4	1		1

我們再次從堆疊中彈出最後一個函式呼叫，留下函式呼叫 1，factorial(4) 和第 3 行。

return 4 * factorial(3)

我們知道從前面的返回值 factorial(3) = 6。因此 factorial(4) 返回 4 * 6 = 24。

函式呼叫	n	返回行	返回值
1	4	3	24
2	3	3	6
3	2	3	2
4	1		1

我們到達了函式呼叫 1 的末尾。但是我們現在要去哪裡呢？堆疊上沒有剩下任何東西，我們已經完成了程式碼。因此結果是 24。

斐波那契數列示例

斐波那契數列在自然界中被發現，幾個世紀以來一直吸引著數學家。

另一個很好的例子是計算 斐波那契數列 的方法。根據定義，前兩個斐波那契數列為 0 和 1，並且每個後續數字都是前兩個數字的總和。

$0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots \;$

例如，取第 6 個數字 5。這是第 5 個數字 3 和第 4 個數字 2 的總和。

在數學術語中，斐波那契數列 F_n 由遞迴語句定義

$F_{n}=F_{n-1}+F_{n-2},\!\,$

前兩個值為

$F_{0}=0\quad {\text{and}}\quad F_{1}=1.$

讓我們嘗試建立一個程式碼版本

答案
function fib(n as integer) select case n case 0 return 0 case 1 return 1 case else return fib(n-1) + fib(n-2) end select end function

遞迴總結

但是，遞迴確實存在一些問題，請考慮我們僅僅為 4 個函式呼叫在堆疊上儲存了多少資料。如果我們要執行 1000 次，使用的記憶體將非常大。

遞迴可以為問題產生更簡單、更自然的解決方案

遞迴佔用大量計算機資源來儲存返回地址和狀態

練習：遞迴 定義遞迴 答案 用自身來定義一個子例程 給出以下遞迴函式呼叫 recur(6) 的輸出。 function recur(ByVal n as integer) console.writeline(n) if n > 0 then recur(n-1) else return 0 end if end function 答案 6 5 4 3 2 1 0 給出以下遞迴函式呼叫 recur(4) 的輸出。 function recur(ByVal n as integer) if n > 0 then recur(n-1) else return 0 end if console.writeline(n) end function 答案 1 2 3 4 給出以下遞迴函式呼叫 recur(6) 的輸出。 function recur(ByVal n as integer) if n <= 10 then recur(n+1) else return 0 end if console.writeline(n) end function 答案 10 9 8 7 6 為以下遞迴函式繪製一個跟蹤表。 答案 說出遞迴解決方案的一個優點和一個缺點。 答案 遞迴可以為問題產生更簡單、更自然的解決方案。 遞迴佔用大量計算機資源來儲存返回地址和狀態。