从EcmaScript角度进行功能编程。 递归及其类型

哈Ha！

今天，我们继续在EcmaScript上下文中进行函数式编程的研究，EcmaScript的规范基于JavaScript。 在本周期的前几篇文章中，考虑了以下主题：

1. 纯函数，λ，抗扰度
2. 组成，咖喱，部分涂抹

递归

与往常一样，维基百科帮助我们找到定义：

递归-对象或过程本身内部的对象或过程的定义，描述，图像，即对象是其自身一部分的情况。 术语“递归”用于各种特殊的知识领域-从语言学到逻辑学，但在数学和计算机科学中应用最为广泛。

对于编程，递归是指在其体内调用自身的过程 。 递归函数具有几个强制性组件：

• 终端条件 -终止条件
• 深入递归的规则

考虑最流行的递归示例-阶乘计算。

const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); } 

我们区分递归函数的特征部分。 终端条件

  if (n === 0) { return 1; } 

和递归规则

 return n * factorial(n - 1); 

重要的是要认识到递归不是JS的某些特定功能，而是编程中非常普遍的技术。

递归和迭代过程

递归可以通过两种方式来组织：通过递归过程或通过迭代过程。

我们已经看到了递归过程：

 const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); } 

阶乘问题的迭代解决方案如下所示：

 const factorial = (n) => { const iter = (counter, acc) => { if (counter === 1) { return acc; } return iter(counter - 1, counter * acc); }; return iter(n, 1); }; 

这两个选项都是递归的。 两种解决方案都具有递归的特征：终端条件和沿着递归的运动规则。 让我们看看它们之间的差异。

每个步骤的递归过程都会记住该动作。 需要做的。 达到高温条件后，他以相反的顺序执行所有记忆的动作。 让我们举例说明。 当递归过程考虑阶乘6时，它需要记住5个数字，以便最后才对它们进行计数，这时您无法到达任何地方，也无法再深入。 当我们在下一个函数调用中，在此调用之外的某个位置，这些记忆的数字将存储在内存中。

看起来像这样：

 factorial(3); // 6  ,    3 3 * factorial(2); 3 * 2 * factorial(1); 3 * 2 * 1; 3 * 2; 6; 

如您所见，递归过程的基本思想是将计算推迟到最后。
这样的过程会生成随时间变化的状态 ，该状态存储在当前函数调用之外的“某处”。

我想您还记得在函数编程系列的第一篇文章中，我们谈到了抗扰性和缺乏状态的重要性。 患病会引发许多并非总是易于解决的问题。

迭代过程与递归 过程 在固定数量的状态上有所不同。 在每一步中，迭代过程都会考虑它可以计算的所有内容，因此递归的每一步都独立于上一步而存在。

看起来像这样：

 iter(3, 1); // iter(3 - 1, 1 * 3); // ,      6, iter(2, 3); // iter(2 - 1, 2 * 3);//   ,      3 iter(1, 6); // counter === 1, return 6 6; 

我认为很明显，迭代过程消耗的内存更少。 因此，在创建递归时应始终使用它。 唯一的例外：如果在达到热条件之前无法计算值。

树递归

许多人认为树木和与树木一起工作是非常深刻，复杂且仅仅是凡人难以理解的事情。 实际上并非如此。 任何层次结构都可以树的形式表示。 甚至人类的思维也像一棵树。

为了更好地理解树的递归，让我们看一个简单而流行的示例-斐波那契数。

斐波那契数-数值序列的元素0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765、10946， 17711，...（OEIS中的序列A000045），其中前两个数字是1和1或0和1，并且每个后续数字等于两个先前数字的总和。 以比萨的中世纪数学家莱昂纳多（Leonaardo）命名（称为斐波那契）。

从数学上讲，对这个序列进行描述很简单（而声明式编程就是描述）：

 fib(n) = [  0  n = 0,//(1)  1  n = 1,//(2) fib(n-1) + fib(n-2)     ] 

现在让我们从数学转向逻辑推理（毕竟，我们需要编写程序逻辑）。 要计算fib（5），我们必须计算fib（4）和fib（3）。 要计算fib（4），我们必须计算fib（3）和fib（2）。 要计算fib（3），我们必须计算fib（2），依此类推，直到获得数学模型中的已知值（1）和（2）。

我们的推理应该带给我们什么想法？ 显然，我们应该使用递归。 可以将热条件公式化为n <=1。但是，代替递归的一个分支（如前面的示例一样），我们将有两个分支：fib（n-1），fib（n-2）。

 const fib = (n) => (n <= 1 ? n : fib(n - 1) + fib(n - 2)); 

这个解决方案有一个很大的缺点！ 它在不同分支中多次考虑相同n值的结果。 为了解决此问题，有一种称为备忘录的功能编程技术，我们将在以下文章之一中进行讨论。

结论

递归是一种非常强大的编程工具。 让我提醒您，通常，我们使用迭代过程。 仅当我们无法在递归的每个步骤中计算中间结果时，才需要使用递归过程。