从基础到中级：递归

概述

此处提供的材料仅用于教育目的。在任何情况下，除了学习和掌握所提出的概念外，都不应出于任何目的使用此应用程序。

在上一篇文章从基础到中级：联合（二）中，我们探索了如何使用联合来解决许多人声称使用纯粹简单的 MQL5 不可能解决的问题。

亲爱的读者，虽然你们中的许多人可能会认为这种任务只能由经验丰富的程序员完成，但在我看来和理解中，我们所涵盖的是基本材料。任何初级编程学生都可以完全实现。

我们现在正进入一个事物开始迅速扩展的阶段，为应用和探索提供了许多可能性。尽管许多人仍然对深入研究可能看起来大胆或先进的编程犹豫不决，但我们到目前为止所涵盖的内容证明，只要我们现在不涉及事件，就确实有可能对各种解决方案进行编程，因为我们还没有涵盖如何正确使用和实现它们。

值得再次强调的是，MetaTrader 5 是一个事件驱动的平台，其中运行的应用程序也是基于事件的 —— 除了两种通常不依赖于事件的类型。这些是作为附件包含的脚本和服务。我们将在更合适的时候探索服务，因为与它们合作需要更深入地了解 MetaTrader 5 的运作方式。在我看来，服务是 MetaTrader 5 可以构建的最先进的应用程序类型。

除了这两种类型之外，我们还有指标和 EA 交易。两种类型都是围绕事件驱动编程设计的。目前还不适合详细讨论这些问题。然而，还有其他几个主题需要涵盖，我认为这对于为任何有抱负的金融市场编程专业人士打下坚实的基础至关重要。

我提到这一点是因为许多人认为他们已经准备好进入这个领域，但当受到考验时，他们惨遭失败，经常指责世界不公平。然而，事实是，他们根本没有充分准备好面对一个有能力的程序员可以轻松、快速和高效地处理的挑战。

一种特殊的循环

在几篇文章中，我解释了与使用循环相关的命令。在 MQL5 中，与许多其他语言一样，我们通常有三种类型的循环。在我看来，最简单的是 “while” 和 “do...while”。除此之外，我们还有 “for” 循环。然而，事实上，还有第四种创建循环的方法，几乎每种编程语言都有这种方法。我记得唯一缺乏对它的支持的是 BASIC。这是因为 BASIC 不是一种设计用于处理函数和过程的结构化语言。但这在这里无关紧要，因为我们正在使用 MQL5，一种完全支持函数和过程的结构化语言。这就引出了循环的第四种形式。

通常，循环是通过以下两种方式之一创建的：使用专用的循环控制结构或使用函数或过程。是的，亲爱的读者，使用函数或过程来创建循环听起来可能很奇怪。然而，这比你想象的要普遍得多。

当我们使用循环构造来创建重复时，我们称之为迭代编程。当我们出于同样的目的使用函数或过程时，这被称为递归编程。了解如何创建和应用递归是每个初学者都应该学习的 —— 在许多情况下，递归循环更容易理解。

那么，为什么我现在才提起这件事呢？因为在代码中有效地使用递归需要对一些关键概念有扎实的理解：“if” 语句、变量和常量的正确使用、理解生命周期和值传递，最重要的是，对数据类型及其局限性有深刻的理解。根据你正在做的事情，选择最合适的类型很重要。这将帮助您避免可能阻碍递归操作的歧义。

考虑一下：与迭代循环不同，迭代循环通常位于您正在处理的代码附近，递归循环的关键部分可能位于远离您当前阅读位置的函数或过程中。如果发生错误或失败，您通常需要跟踪整个代码，以找到一切开始返回的原点。由于递归的本质，这并不总是初学者可以处理的任务。乍一看它似乎不像一个循环，但事实上它确实是一个循环，只是一种特殊的循环。

为了更好地理解这一点，我们需要看一个实际的例子。但在我们这样做之前，还有一点要注意：任何迭代循环都可以被重写为递归循环，任何递归循环都可以重写为迭代循环。然而，将一个转换为另一个的难度取决于循环本身的性质。一般来说，迭代循环在执行过程中表现更好。递归循环通常更容易编程。因此，一个可以弥补另一个。将递归循环转换为迭代循环所花费的时间可能不值得获得性能提升。因此，经验法则是追求简单性和最低成本。话虽如此，我们开始吧。

我们将从一个非常简单的例子开始，只是为了更容易理解这在实践中是如何工作的。就是这个。

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     Recursive(5);
07. }
08. //+------------------------------------------------------------------+
09. void Recursive(uchar arg)
10. {
11.     Print(__FUNCTION__, " ", __LINE__, "  :: ", arg);
12.     arg--;
13.     if (arg > 0)
14.         Recursive(arg);
15.     Print(__FUNCTION__, " ", __LINE__, "  :: ", arg);
16. }
17. //+------------------------------------------------------------------+

代码 01

当执行此代码 01 时，它将产生下图所示的结果。

图 01

但这是什么？怎么这么疯狂？好吧，这正是递归例程所做的。起初，这可能看起来有点疯狂，但通常，这正是我们想要的。您会注意到，图 01 中所示的相同输出可能是使用传统循环生成的。然而，在这个例子中，它是使用称为递归的概念生成的。也就是说，当一个函数或过程调用自己或另一个函数、过程，意图在它们之间形成循环时。许多人将递归严格地与调用自身的单个函数或过程联系在一起。但事实并非一定如此。唯一的要求是，在不使用任何标准循环命令的情况下形成循环。下面显示了另一个有趣的递归示例：

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     Print("Result: ", Fibonacci(7));
07. }
08. //+------------------------------------------------------------------+
09. uint Fibonacci(uint arg)
10. {
11.     if (arg <= 1)
12.         return arg;
13. 
14.     Print(__FUNCTION__, " ", __LINE__, "  :: ", arg);
15. 
16.     return Fibonacci(arg - 1) + Fibonacci(arg - 2);
17. }
18. //+------------------------------------------------------------------+

代码 02

这可能是研究递归时使用的最经典的例子。这是因为代码 02 清楚地演示了递归的工作原理。执行时，它会产生如下所示的结果：

图 02

换句话说，斐波那契数列中的第 7 个值是 13。事实上，如果你熟悉这个序列，你就知道这是正确的。但是，这段代码究竟是如何计算第 7 个值的呢？说实话，目前可能还不清楚这是如何实现的。亲爱的读者，关键在于第 16 行，其中包含计算斐波那契数所需的最小分解。如果你查找用于计算斐波那契值的数学表达式，你会发现类似于下面所示的内容。

图 03

现在，再看一下第 16 行。你能发现图 03 中的数学表达式和第 16 行所写内容的相似之处吗？这正是递归例程的基础。也就是说，我们不断分解问题，直到答案收敛到最小已知值。那么最小值是多少？对于斐波那契数列来说，该值要么是 0，要么是 1。这就是我们在第 11 行检查的内容。

请注意：就像在代码 01 中一样，我们首先有一个倒数（下降序列），然后是一个看似正数的过程（上升序列）。相同的模式出现在代码 02 中，但分为两个不同的阶段。第一阶段计算 arg-1 的值。进行一系列函数调用，直到最终到达第 12 行。每次调用时，都会执行第 14 行并打印 arg 的当前值。因此，我们最初观察到一个递减的顺序，每一步一个单位。一旦所有这些调用开始返回，函数就会再次开始调用自己，这次减少了两个单位。我明白这可能看起来仍然相当复杂。因此，为了使事情更容易形象化并更好地理解代码 02 如何成功计算结果，我们将修改其中的一些部分。更新后的版本如下所示：

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     Print("Result: ", Fibonacci(5, 0, 0));
07. }
08. //+------------------------------------------------------------------+
09. uint Fibonacci(uint arg, uint call, int who)
10. {
11.     uint value = 0;
12. 
13.     Print(__FUNCTION__, " ", __LINE__, " Entry point [ ", call," ]  ARG: ", arg, " WHO: ", who);
14. 
15.     if (arg <= 1)
16.     {
17.         Print(__FUNCTION__, " ", __LINE__, " Number Callback [ ", call," ]  ARG: ", arg, " WHO: ", who);
18. 
19.         return arg;
20.     }
21. 
22.     value += Fibonacci(arg - 1, call + 1, 1);
23. 
24.     Print(__FUNCTION__, " ", __LINE__, " Value = ", value, "  >> New call with arg: ", arg);
25. 
26.     value += Fibonacci(arg - 2, call + 1, 2);
27. 
28.     Print(__FUNCTION__, " ", __LINE__, " General Return = ", value);
29. 
30.     return value;
31. }
32. //+------------------------------------------------------------------+

代码 03

此时此刻，我必须向大家道歉。但不幸的是，没有更简单的方法来解释这里发生的事情。执行代码 03的输出如下：

图 04

我知道图 04 相当长。但是，请注意，我已经将函数调用从计算 7 个元素更改为计算 5 个元素。虽然这看起来并不多，但它大大减少了这里需要分析的信息量。尽管如此，还是有一些非常重要的事情需要考虑。每次执行第 13 行时，我们都会进入函数。这可能会导致立即返回或另一次递归调用。一开始可能会让人感到困惑的一个细节是第 11 行的条件。许多人可能会认为这会干扰最终结果。但如果你相信这一点，这可能意味着你还没有完全掌握递归对函数或过程的实际作用。

这就是我尽可能详细地展示图 04 的原因。我想帮助您真正了解正在发生的事情，以及代码 02 如何计算出正确的结果。

由于以下内容需要您全神贯注，亲爱的读者，我恳请您在继续之前排除任何干扰。递归函数或过程可能会变得令人困惑，尤其是在编程中第一次遇到它们时。

现在，根据图 04，让我们了解一下到底发生了什么。首先，当执行第 6 行时，我们调用斐波那契函数，就好像它是一个循环一样。不是迭代循环，而是递归循环。这是你必须理解的第一个关键点。

下一点是认识到限制条件是必要的，正如我们在代码 01 中看到的那样。任何使用递归的循环都必须有一个停止条件。在本例中，该条件在第 15 行设置。我知道前面提到过，递归应该简化为一个简单的表达式，但限制递归的作用与该表达式无关。这是不同的概念。这是一个重要的时刻。让我澄清一下： 

生成递归的是最小数学表达式的实现。限制递归的是防止它成为无限循环的条件。

因此，在代码 04 中，限制条件位于第 15 行。递归机制由第 22 行和第 26 行创建。在代码 02 中，限制条件是第 11 行，递归由第 16 行触发。

现在让我们了解一下它的工作原理。我们的初始参数是 5。这会触发第 13 行，然后是第 22 行。此行再次调用该函数，回到第 9 行，创建一个循环。但请注意：在第 22 行的调用期间，参数减少了 1。因此，我们的调用堆栈开始构建 —— 一次又一次的调用 —— 直到第 15 行变为 true。

就在这时，有趣的事情发生了。这是第 4 次调用，参数值正在减小。当第 15 行变为 true 时，将执行第 17 行，向我们显示当前参数值以及该函数被调用的次数。由于参数现在是 1，我们将该值返回给调用者。但调用者不是第 6 行，而是第 22 行。请记住，我们已经堆叠了多个调用。现在我们开始解开堆栈。返回的第一个值是 1，并将其添加到变量 Value 中。此变量在调用之间不会丢失其值，因为它会累积并在每次返回时建立一个新值。为了更好地理解这一点，您需要知道调用栈是如何工作的，但就目前而言，这是一个更高级的主题。别担心，因为你仍然可以遵循递归的核心思想。你只需要小心一点。

现在，我们已经计算了第一个返回值。但是，如图 03 中的表达式所示，我们仍然需要进行另一次递归调用。为此，我们在第 26 行进行了一次新的调用。这就是事情变得棘手的地方。

第 22 行的调用每次都会将值减少 1。但是当 arg 达到 1 并且函数返回时，前一次调用（第 22 行）中的 arg 仍然为 2。因此，当我们移动到第 24 行时，尽管 arg 在最近的调用中为 1，但现在 arg = 2。

一开始这可能会让人感到困惑。这就是我使用最简单的递归示例的原因：斐波那契。为什么我们在查看代码 01 时，首先看到的是倒数，然后是看起来像是正数的内容。之所以会发生这种计数，是因为我们之前已经堆叠了值。所以当我们开始解开这些值时，我们得到了一个升序的错觉，尽管它没有直接实现。这种行为纯粹是递归调用堆叠和返回方式的副作用。

好吧，我们谨慎行事。在第 26 行，此时 arg 为 2。当减少 2 时，它变为 0。这导致第 15 行返回 true，并且函数返回 0。因此，第 28 行打印返回值为 1。这是第一个元素的斐波那契值。

请记住，我们调用了 5 次，但只返回了一次。现在，回到第 22 行，Value 变为 1。但它不是已经是 1 了吗？不，亲爱的读者。这是在之前的调用中。现在我们回到第 22 行，其中 Value 为 0。现在变成了 1。然后我们执行第 24 行。当我们解除另一个调用时，arg 现在为 2。这一刻发生在第 24 行，请仔细遵循操作顺序。因此我们减去 2（第 26 行），使得传递给函数的参数为 0。而 WHO 仍是 2。这是因为我们从第 26 行开始调用该函数。

由于 arg 为 0，因此第 15 行为 true，并在第 19 行返回 0。回到第 26 行，我们将这个结果 (0) 添加到我们之前的值 (1)。所以现在 Value 为 1。这是第二个斐波那契数。

现在我们回到第 22 行，我们只解除了五个调用中的两个。这次，Value 为 1，arg 为 3。这是有趣的部分：arg = 3。减去 2（第 26 行）得到 1，因此使用 arg = 1 调用该函数。这将触发第 15 行，并返回 1。现在 Value 为 2。

这是第三个斐波那契数。解开另一个层面：回到第 22 行，Value = 2，arg = 4。当执行第 26 行时会发生什么？你猜到了吗？该函数再次被调用，但 arg = 2。请记住，在调用函数之前，我们在第 26 行减去 2。

因此，由于此时 arg 为 2，第 15 行将失败，第 22 行将再次执行。只是此时 Value 变量为 0，而不是 2。该其他值已保存在堆栈中。由于 arg = 2 并且我们需要在调用之前减 1，因此在第 15 行 arg 将为 1 并且将返回 1。现在第 22 行的 Value = 1，因此将执行第 26 行。此时，当从 arg 中减去 2 时，会调用该函数并减去 2。这将返回 0。而第 30 行会返回值 1，但是它会返回到哪里呢？这将带您回到第 26 行，即进行该调用的地方。请记住，值当前为 2。由于有一次返回，因此 Value 现在为 3。所以我们刚刚计算了序列的第四个元素。只缺一个。（笑）

此时，我想你的大脑可能会感觉像陷入了困境 —— 如此多的调用，如此多的返回。但对于最后一个元素，我们跳过重复。您已经了解了所有必要的机制。所以现在，在第 26 行，arg = 5 且 Value = 3。由于需要将 arg 减半，因此需要进行一系列新的调用。我想我们已经解释了你需要理解的一切。

重要的是我们在本文开头所说的：递归易于编码，但执行速度较慢。这就是为什么我们可以构建一个等效的迭代版本来计算斐波那契数。虽然代码变得有点复杂，但这会带来更好的性能。

为了证明这一点，现在让我们来看看如何使用迭代而不是递归来实现同样的计算。有很多方法可以做到这一点，下面是其中一种方法：

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     const uchar who = 6;
07. 
08.     Print("Result: ", Fibonacci_Recursive(who));
09.     Print("Result: ", Fibonacci_Interactive(who));
10. }
11. //+------------------------------------------------------------------+
12. uint Fibonacci_Recursive(uint arg)
13. {
14.     if (arg <= 1)
15.         return arg;
16. 
17.     return Fibonacci_Recursive(arg - 1) +  Fibonacci_Recursive(arg - 2);
18. }
19. //+------------------------------------------------------------------+
20. uint Fibonacci_Interactive(uint arg)
21. {
22.     uint v, i, c;
23. 
24.     for (c = 0, i = 0, v = 1; c < arg; i += v, c += 2)
25.         v += i;
26. 
27.     return (c == arg ? i : v);
28. }
29. //+------------------------------------------------------------------+

代码 04

请注意，这里我们使用的是两种循环方法。第一个是递归，第二个是迭代。现在我问你：你觉得哪一个更容易理解？根据您的回答，您认为哪个执行时间更快？根据您对执行相同类型计算的两种方法的了解来考虑这一点。

由于我知道一些读者可能会发现从第 20 行开始实现的迭代函数有点不寻常，让我简要解释一下它是如何工作的。

在第 22 行，我们声明所需的变量。然后，在第 24 行，我们进入计算的主循环。这就是事情变得有趣的地方。请注意，我们在执行任何计算之前都会初始化这些值。现在有一个关键点：当我们要查找的元素是奇数（第一、第三、第五、第七个元素，以此类推）时，变量 v 会得到正确的结果。然而，当所寻找的元素是偶数时，变量 i 会保持正确的值。为什么呢？

原因是计数器变量 c 在每次迭代时都会增加 2，以防止超出正确结果。由于每次迭代都会将之前的值添加到一个新的值中，并且我们不会在 i 和 v 之间交换值，因此在我们的迭代函数中会出现这种细微的区别。有可能以避免这个特定问题的方式实现这一点，但我认为这是不必要的。循环交互已经告诉我当前和下一个值。因此，我需要做的就是应用三元运算符来返回正确的结果。如果没有这个小的调整，我们最终可能会指向序列中的下一个元素或前一个元素，这取决于输入（或所查找的元素）是奇数还是偶数；以及我们是否返回 i 或 v 的值。

为了证明此代码 04 确实有效，我们在下面立即包含了它的输出。要测试其他值并比较两种计算斐波那契数列的方法，只需更改第 6 行中的常数即可。但请记住，斐波那契数列增长非常快。由于代码中使用的类型存在局限性，请注意不要在序列的末尾请求太多的值，这样做可能会导致意外的结果甚至错误。

图 05

有一些方法可以克服这些限制，使我们能够计算计算机内存容量内的任何数字。然而，这是一个更高级的话题，在我看来，最好留到更合适的时间。但只是为了激发您的好奇心：您认为程序员如何能够计算 π（pi）或其他具有数千位小数的无理常数的值？毕竟，大多数编程语言中使用的标准数据类型远不能达到这种精度。

正如我提到的，这个话题需要更深入的理解。这并不是说我们到目前为止所掌握的知识完全无法企及，因为事实并非如此。事实上，是的，使用我们在这里讨论的概念，包括递归，可以实现这样的计算。然而，实现它需要付出更多的努力，因为您需要将各种组件调整为不直观的格式。

最后的探讨

本文旨在介绍一个强大且真正令人愉快的编程概念。但这是一个必须谨慎和尊重的问题。对递归的理解不足或误用可能会将相对简单的程序变成不必要的复杂程序。然而，当在正确的情况下正确使用时，递归成为解决问题的有力盟友，否则这些问题将变得更加困难或耗时。

一般来说，尽可能使用递归，特别是在处理不容易迭代求解的数学表达式时。但请记住：多次递归调用的高昂成本可能会减慢程序的速度。当性能成为问题时，考虑将递归逻辑重写为迭代循环。虽然最初设计起来更复杂，但迭代解决方案在执行过程中往往要快得多，特别是在处理需要转换的大型数据集或序列时。