Sway 參考手冊/遞迴
在上一章中，我們學習了使用while、do-until、for 和for-each 函式進行迴圈。這些函式實現了被稱為迭代迴圈的東西。
遞迴是另一種迴圈方式；通常，與while和for等迭代迴圈相比，遞迴迴圈更容易編寫和理解。許多數學函式很容易遞迴實現，所以我們將從那裡開始。回想一下，一個數字n的階乘是
考慮編寫一個函式，該函式計算正整數的階乘。例如，如果該函式傳遞的值為 4，它應該返回 24 的值，因為 4！是 4*3*2*1 或 24。一種方法是使用迭代迴圈遍歷所有乘數，在每次迭代時儲存部分乘積。使程式碼正常工作確實需要一些調整才能使所有重要的部分都正確。一個有效的實現可能看起來像
function factorial(n)
{
var i;
var product = 1;
for (i = 1, i <= n, i = i + 1)
{
product = product * i;
}
product;
}
此實現提出了許多問題，因為它違反了結構化計數迴圈的一般約定
- 為什麼乘積初始化為 1 而不是 0？
- 為什麼迴圈初始化選擇為 而不是 ？
- 為什麼迴圈測試為 而不是 ？
經過一番思考，這些問題可以根據乘法的數學原理得到解答。
有一種完全不同的方法可以使用，一種極其簡單、優雅且強大的方法，稱為遞迴。要應用遞迴來解決問題，必須能夠用更簡單的術語來描述問題的解決方案。對於階乘，一個數字的階乘可以用更簡單的階乘來描述。
otherwise
第二個公式指出，零的階乘為一。 [1] 並且任何其他（正）數字的階乘是透過將該數字乘以比該數字小 1 的數字的階乘獲得的。經過一番研究，您應該能夠看到第一個公式（帶有省略號 ...）和這個新公式是等效的 [2]。第二種形式特別適合作為計算機程式實現
function factorial(n)
{
if (n == 0)
{
1;
}
else
{
n * factorial(n - 1);
}
}
或
function factorial(n)
{
if (n == 0,1,n * factorial(n - 1));
}
使用if的純函式呼叫語法。
請注意，這兩個版本的factorial是如何精確地實現了第二個公式的。
透過跟蹤函式呼叫，說服自己該函式確實有效
factorial(3)
分解呼叫，我們發現
factorial(3) is 3 * factorial(2)
因為n的值為 3，不等於 0。因此，if的第二個程式碼塊被評估。我們可以替換factorial(2)透過2 * factorial(1)，產生
factorial(3) is 3 * 2 * factorial(1)
因為n的值現在為 2，仍然不為零。繼續沿著這條路線，我們可以替換factorial(1)透過1 * factorial(0)，產生
factorial(3) is 3 * 2 * 1 * factorial(0)
現在，在對 factorial 的這個呼叫中，n 的值確實為零，所以我們可以替換factorial(0)使用它直接的返回值零
factorial(3) is 3 * 2 * 1 * 1
因此，factorial(3)的值為六
sway> factorial(3); INTEGER: 6
正如預期。
遞迴函式的組成部分
[edit | edit source]遞迴方法依賴於這樣一個事實：解決較小的問題通常比解決較大問題更容易。在階乘問題中，嘗試找到階乘n - 1 比找到階乘n 更簡單一些。如果找到階乘n - 1 仍然太難以輕鬆解決，那麼找到階乘n - 2，依此類推，直到我們找到一個易於解決的情況。關於階乘，這是當n 等於零時。'易於解決'的程式碼（以及使您達到那裡的值）被稱為基本情況。找到較簡單問題的解決方案的程式碼（以及使您達到那裡的值）被稱為遞迴情況。遞迴情況通常包含對正在執行的同一函式的呼叫。此呼叫被稱為遞迴呼叫。
大多數形式良好的遞迴函式至少包含一個基本情況和至少一個遞迴情況。
最大公約數
[edit | edit source]考慮找到兩個數字的最大公約數 (gcd)。一種方法是使用重複除法。第一次除法將這兩個數字相除，儲存餘數。現在使除數成為被除數，餘數成為除數。重複此過程，直到餘數為零。此時，當前除數就是 gcd。
讓我們先將其迭代地轉換成一個函式，然後遞迴地轉換成一個函式。
// compute the gcd of two positive integers iteratively
function gcd(first,second)
{
var remainder;
do-until (remainder == 0)
{
remainder = first % second;
first = second;
second = remainder;
}
first; //first holds the last divisor
}
do-until 迴圈確保在測試餘數之前執行迴圈主體。讓我們遞迴地重寫該函式。首先，我們識別遞迴情況，然後識別基本情況。在本例中，遞迴情況和基本情況與階乘示例略有不同。如果餘數不為零，我們遞迴 [3]。如果餘數為零，我們立即返回答案。現在，遞迴情況和基本情況已經確定，我們可以輕鬆地編寫遞迴版本。
// compute the gcd of two positive integers
function gcd(first,second)
{
if (first % second == 0)
{
second;
}
else
{
gcd(second,first % second);
}
}
或
function gcd(first,second)
{
if (first % second == 0,second,gcd(second,first % second));
}
或者，要刪除對餘數的重複計算
function gcd(first,second)
{
var remainder = first % second;
if (remainder == 0,second,gcd(second,remainder));
}
同樣，遞迴版本更加緊湊。
請檢視遞迴版本是如何透過將second作為第一個引數傳遞到遞迴呼叫中來將second 轉換為first 的。同樣，remainder 由於是遞迴呼叫中的第二個引數，因此變成了second。為了說服自己該例程確實有效，修改gcd 以檢查引數
function gcd(first,second)
{
var remainder = first % second;
inspect(array(first,second,remainder));
if (remainder == 0,second,gcd(second,remainder));
}
您還沒有學習陣列或內建的array 函式，但將其視為將多個事物組合在一起的一種方式。檢查陣列是一種技巧，可以在一次呼叫inspect時檢查多個值。
sway> gcd(66,42); array(first,second,remainder) is [66,42,24] array(first,second,remainder) is [42,24,18] array(first,second,remainder) is [24,18,6] array(first,second,remainder) is [18,6,0] INTEGER: 6
請注意，第一個餘數 24 是如何不斷地向左移動的。在第一次遞迴呼叫中，餘數變成second，因此 24 向左移動一個位置。在第二次遞迴呼叫中，當前的second，即 24，變成first，因此 24 再次向左移動。
斐波那契數列
[edit | edit source]遞迴的第三個例子是計算 斐波那契數。斐波那契數列看起來像這樣
n 0 1 2 3 4 5 6 7 8 ... Fib(n) 0 1 1 2 3 5 8 13 21 ...
並且在自然界中一次又一次地出現 [4].. 一般來說，斐波那契數等於前兩個斐波那契數的總和。例外是零和第一個斐波那契數，它們分別等於 0 和 1。瞧！遞迴情況和兩個基本情況已經跳出來了！那麼，這是一個計算第 n 個斐波那契數的遞迴函式的實現。
// compute the nth Fibonacci number
// n must be non-negative!
function fibonacci(n)
{
if (n == 0) return 0;
if (n == 1) return 1;
fibonacci(n-1) + fibonacci(n-2);
}
我們的實現簡單而優雅。不幸的是，它效率極低。與我們的factorial 和gcd 遞迴版本不同，這些版本遞迴的次數與迭代版本的迴圈次數一樣多，當計算較大的斐波那契數時，我們的斐波那契版本將比斐波那契的迭代版本遞迴的次數多得多。原因如下。
考慮呼叫fib(6). 追蹤所有遞迴呼叫到 fib，我們得到
fib(6) is fib(5) + fib(4)
替換fib(5)為fib(4) + fib(3), 我們得到
fib(6) is fib(4) + fib(3) + fib(4)
我們已經可以看到一個問題，我們將計算兩次 fib(4)，一次來自對 fib(6) 的原始呼叫，另一次是在我們嘗試找到 fib(5) 時。如果我們寫下對fib(6)所有遞迴呼叫，每個遞迴呼叫從前一個遞迴呼叫縮排，我們得到一個看起來像這樣的結構
fib(6)
fib(5)
fib(4)
fib(3)
fib(2)
fib(1)
fib(0)
fib(1)
fib(2)
fib(1)
fib(0)
fib(3)
fib(2)
fib(1)
fib(0)
fib(1)
fib(4)
fib(3)
fib(2)
fib(1)
fib(0)
fib(1)
fib(2)
fib(1)
fib(0)
我們預計，根據斐波那契數列的生成方式，需要大約六個“步驟”來計算fib(6). 相反，最終有 13 次呼叫fib(1)或fib(0)[5]. 存在大量的重複工作，因此是浪費的努力。所以讓我們嘗試使用迭代迴圈來計算斐波那契數。
function fib(n)
{
var i;
var first = 0;
var second = 1;
for (i = 0, i < n, i = i + 1)
{
var sum = first + second;
first = second;
second = sum;
}
first;
}
在迴圈體中，我們看到 fib 很像 gcd；第二個數字成為第一個數字，第一個和第二個數字的某種組合成為第二個數字。對於 gcd，組合是餘數，對於 fib，組合是總和。
與階乘一樣，找到迭代執行的正確方法並不完全直觀，而遞迴版本幾乎是自寫的。注意到 fib 和 gcd 的相似性表明了一種同時具有遞迴和效率的方法。
為了將迭代迴圈轉換為遞迴迴圈，首先要識別在迴圈體中發生更改的那些變數；這些變數將成為遞迴函式中的形式引數。例如，上面的 fib 迴圈有三個（不是兩個！）變數在迴圈的每次迭代期間發生更改：first、second 和 i。所以，我們這樣開始我們的遞迴函式
function loop(first,second,i)
{
...
}
迴圈測試成為 loop 函式體中的 if 測試
function loop(first,second,i)
{
if (i < n)
{
...
}
else
{
...
}
}
if-true 塊成為遞迴呼叫。遞迴呼叫的引數對迴圈變數的更新進行編碼。if-false 塊成為迴圈試圖計算的值
function loop(first,second,i)
{
if (i < n)
{
loop(second,first + second,i + 1);
}
else
{
first;
}
}
使用函式呼叫語法來表示 if 可以縮短函式
function loop(first,second,i)
{
if (i < n,loop(second,first + second,i + 1),first);
}
接下來，我們將 loop 函式嵌入到包含原始迴圈的函式中。這樣，原始迴圈的測試或主體中引用的任何非區域性變數都將對 loop 函式可見
function fib(n)
{
function loop(first,second,i)
{
if (i < n,loop(second,first + second,i + 1),first);
}
...
}
最後，我們使用迴圈變數的初始值呼叫 loop 函式
function fib(n)
{
function loop(first,second,i)
{
if (i < n,loop(second,first + second,i + 1),first);
}
loop(0,1,0);
}
為了更多練習，讓我們使用這種方法將 factorial 的迭代版本轉換為遞迴函式。我們將看到，我們將得到一個與以前不同的遞迴函式。
function factorial(n)
{
var i;
var product = 1;
for (i = 1, i <= n, i = i + 1)
{
product = product * i;
}
product;
}
我們像以前一樣，從處理 loop 函式開始。在這種情況下，迴圈中只有兩個變數發生變化：product 和 i。
function loop(product,i)
{
...
}
接下來，我們寫下 if 表示式
function loop(product,i)
{
if (i <= n,loop(product * i,i + 1),product);
}
接下來，我們嵌入 loop 函式並呼叫它
function factorial(n)
{
function loop(product,i)
{
if (i <= n,loop(product * i,i + 1),product);
}
loop(1,1);
}
這個故事的寓意是，任何迭代迴圈都可以重寫為遞迴，任何遞迴都可以重寫為迭代迴圈。此外，在“好的”語言[6]中，沒有理由在執行時間或執行過程中使用的空間方面偏好一種方式而不是另一種方式。如果遞迴使實現更清晰，則使用遞迴；否則，使用迭代迴圈。
- ↑ 數學家們，作為一群包容的人，喜歡邀請零參加階乘派對。
- ↑ 第一個公式傳達了階乘的基本思想，但並不十分精確。例如，如何使用第一個公式計算三的階乘？
- ↑ 這個詞是 recur，而不是 recurse！
- ↑ 菠蘿、黃金分割、鸚鵡螺等。
- ↑ 13 是一個斐波那契數。真奇怪！
- ↑ 總有一天，Sway 會成為一種“好的”語言。