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 会成为一种“好的”语言。