我的解决方案是递归的吗?(学习递归）

Is my solution recursive? (learning recursion)

本文关键字：递归 学习 解决方案 我的      更新时间：2023-09-26

我正在为一个类练习用递归解决问题。

我正在解决此网站上的问题：http://www.w3resource.com/javascript-exercises/javascript-recursion-functions-exercises.php

我所指的问题是：编写一个JavaScript程序来获取范围（x，y）中的整数。示例：范围（2，9）预期输出：[3，4，5，6，7，8]

在研究解决方案之前，我想到了这个：

var range = function (start, end) {
  var result = [];
  var accumulator = start;
  var accumulate = function () {
    accumulator++;
    if (accumulator === end) {
      return;
    } else {
      result.push(accumulator);
    }
    accumulate();
  };
  accumulate();
  return result;
};

网站上的解决方案是：

var range = function(start_num, end_num) 
{
  if (end_num - start_num === 2) 
  {
    return [start_num + 1];
  } 
  else 
  {
    var list = range(start_num, end_num - 1);
    list.push(end_num - 1);
    return list;
  }
};

从技术上讲，我的解决方案仍然是递归的吗？我最近在一次测验中得到了类似的答案，有人告诉我，我的解决方案本质上是迭代的。

尽管您使用递归，但您只是以递归的形式编写了一个循环。

我将从纯粹的学术角度来回答这个问题。如果你想避免中间状态（result）并使用纯函数结构，我会这样写

function range(start, end) {
  function recRange(current, end) {
    if (current > end)
      return [];
    return [current].concat(recRange(current + 1, end));
  }
  return recRange(start + 1, end - 1);
}
console.log(range(2, 9));
// [ 3, 4, 5, 6, 7, 8 ]

如果你看到这里，我们在range函数中创建了一个新函数，它在每次迭代中递归地创建一个新数组（记住：这不是高性能的代码，你可以简单地使用循环并有效地解决这个问题）。

递归的基本条件是current < end。一旦满足该条件，递归将停止，并返回一个空数组。在所有级别中，具有current值的新数组与递归调用的结果连接在一起。因此，对呼叫的评估大致可以理解为这样的

[3].concat(recRange(3 + 1, end));
[3].concat([4].concat(recRange(4 + 1, end)));
...

最后，当递归展开时，值将类似于

[3].concat([4].concat([5].concat([6].concat([7].concat([8].concat([]))))))
[3].concat([4].concat([5].concat([6].concat([7].concat([8])))))
[3].concat([4].concat([5].concat([6].concat([7, 8]))))
[3].concat([4].concat([5].concat([6, 7, 8])))
[3].concat([4].concat([5, 6, 7, 8]))
[3].concat([4, 5, 6, 7, 8])
[3, 4, 5, 6, 7, 8]

并且该结果将被返回。

要使您的解决方案递归，它应该返回一些值，并以某种方式组合递归调用的结果以形成原始调用的返回值。

让我用一个例子来说明这一点，通过修改您的解决方案：

var range = function (start, end) {
  var accumulate = function (accumulator) {
    if (accumulator === end - 1) {
      return [accumulator];  // Stop condition 
    } else {
      // Recursive block
      var result = accumulate(accumulator+1);  // recursive call
      result.unshift(accumulator);  // combine result
      return result
    }
  };
  return accumulate(start);
};

修改后的accumulate函数将为停止条件返回一个单元素列表，这是它处理的最简单的情况，其中accumulator达到要返回的最后一个值。

在示例range(2,9)中，停止条件将返回[8]。

然后在调用者中，递归块

      var result = accumulate(accumulator+1);
      result.unshift(accumulator);
      return result

将获取列表[8]，并预存accumulator的当前值（7），因此它将返回[7,8]。

以及accumulator(7)的调用者，将接收[7,8]，并将值6预绑定到列表中，以返回[6,7,8]。

最后，对accumulator(2)的原始调用将生成预期的结果[2,3,4,5,6,7,8]。

从技术上讲，我的解决方案仍然是递归的吗？

是的。您使用的是尾部递归；然而，由于没有参数被传递给accumulate（），我可以理解为什么有人会说它本质上是迭代的。您可以很容易地将递归调用替换为循环。递归算法通常利用堆栈。

由于Javascript的闭包，与C++、Java或C#等其他语言相比，更难理解Javascript中递归的概念。

要理解递归，必须首先理解递归。：）

相关文章：