递归的JavaScript数组长度

Question

我正在努力理解递归函数式编程的概念。

考虑以下情况（是的，我可以使用.length来获取数组的长度）：

https://jsfiddle.net/ur5gc397/

$(function(){
  function arrLen(arr) {
    var count = 0;

    $.each(arr, function() {
      count = count + 1;
    });

    return count;
  }

  var a = ["a", "b", "c", "d"];

  var lengthOfA = arrLen(a);
})

我希望重新表述这个问题，不想在每次迭代数组时将变量count设置为0，然后再更改它的值。我能否设置某种递归调用自身的函数，并在函数中返回正确的值？

- user479947

---

如果您不将 count 设置为初始值，它将等于 undefined。 - Jongware

var lengthOfA = a.reduce(count => count+1, 0); - Thomas

无论如何，如果不使用“length”属性，则无法处理稀疏数组。 - Thomas

const length = arr => arr.shift() ? 1 + length(arr) : 0 - Xaqron

Answer 1

如果您一定要递归地测试数组的长度，可以按照以下方法进行：

function arrLen(arr) {
    if (!("0" in arr)) { // [].length is banned
        return 0;
    }
    return arrLen(arr.slice(0, -1)) + 1;
}

请注意，这是一个非常愚蠢的想法。

这个想法是，在每次递归时，我们从数组中切掉一个元素（最后一个元素，使用slice(0,-1)），并返回比调用剩余数组上的arrLen多1的值。

序列看起来像这样：

arrLen(["a", "b", "c", "d"])
    calls arrLen(["a", "b", "c"])
        calls arrLen(["a", "b"])
            calls arrLen(["a"])
                calls arrLen([])
                returns 0 == 0
            returns 0 + 1 == 1
        returns 0 + 1 + 1 == 2
    returns 0 + 1 + 1 + 1 == 3
returns 0 + 1 + 1 + 1 + 1 == 4

- lonesomeday

---

哪个更好的 function arrLen(arr){ return 0 in arr? 1+arrLen(arr.slice(1)): 0; } 或者 function arrLen(arr){ function iter(i, count){ return i in arr? iter(i+1, len+1): len } return iter(0, 0) }，这样你就不必使用 slice 函数来切割数组了。 - Thomas

我现在正在使用Lua编程语言，其中使用了这个函数 -- https://dev59.com/7HE85IYBdhLWcg3wl0jF 但是，我想尝试递归并在JavaScript中更好地思考。 - user479947

@Thomas 这个问题的部分思路是我们没有 count 变量。它当然可以写得更简洁，但我试图让它清晰而不是简练。 - lonesomeday

@Thomas 但你是对的，"0" in arr 是一个更好的测试。 - lonesomeday

@lonesomeday，不，问题的一部分是我们没有一个封闭的count变量，在循环中进行递增/变异。在我的代码示例中，没有变异，只有一个函数参数来传递当前计数，因此这是一个可以正确优化的尾调用。 - Thomas

@Thomas 页面底部有一个大蓝色按钮。如果你有更好的解决方案，请随意点击它。 - lonesomeday

Answer 2

我稍微修改了你的代码：

$(function(){
  function arrLen(arr, count) {
  if(!arr[count]) return count;    
    count++;

    return arrLen(arr, count);
  }

  var a = ["a", "b", "c", "d"];
  var lengthOfA = arrLen(a, 1);

  $('body').html(lengthOfA)
})

- Hung Cao

---

嗯，这个已经接近了。也许可以像这样：https://jsfiddle.net/mupordLv/ -- 但是，我不喜欢测试 if (!arr[count])... 我想通过 Each 或 For in 来遍历列表，尽管我不确定如何在这样做时退出递归循环。 - user479947

是的，那也可以。我不知道必须要调用arrLen(a)。 - Hung Cao

你说的“getting through the list”是什么意思？为什么需要它？ - Hung Cao

你能想到一种方法，在不测试失败的越界数组索引的情况下完成这个任务吗？我的限制是我可以为每个数组值运行一个函数，因此我只需要返回函数执行的次数。 - user479947

Answer 3

如果你想使用for/forEach循环，那么递归就没有用武之地了。迭代和递归都是为了达到相同的结果 - 你应该选择其中一种。

迭代：

与您的代码相似，只是简化了一点。保持计数，增加并返回它。

function arrayLength(array) {
  let count = 0;
  for (const i of array) count++;
  return count;
}

console.log(arrayLength([1, 2, 3, 4, 5]));
console.log(arrayLength([]));

递归：

检查数组中的下一个元素是否存在，如果存在，则继续使用下一个索引递归调用函数。该函数返回最后一个索引+1，但对于0是特例。 （请注意，这不适用于稀疏数组，如评论中所述。）

function arrayLength(array, index) {
  index = index || 0;

  if (array[index+1]) {
    return arrayLength(array, index+1);
  } else if (index === 0) {
    return 0;
  } else {
    return index + 1;
  }
}

console.log(arrayLength([1, 2, 3, 4, 5]));
console.log(arrayLength([]));

- skyline3000

Answer 4

在计算一个值时，使用reduce是最好的选择。它并不特别复杂。想象一下你想要对每个元素求和。

[1,2,3,4,5].reduce((a,e) => a+e, 0); // => 15

而 reduce 实际上可以使用递归实现:

Array.prototype.myReduce = function(proc,init) {
  var arr = this;
  var nLen = this.length;
  function helper(acc, nIndex) {
    return nIndex >= nLen ?
           acc :
           helper(proc(acc, arr[nIndex]), nIndex+1); 
  }
  return helper(init, 0);
} 

[1,2,3,4,5].myReduce((a,e) => a+e, 0); // => 15

请注意，实际的实现不会使用递归，因为JS不优化尾递归，因此循环结构将更有效。例如，Ramda是一个函数库，它提供了使用组合制作程序的手段，但在Ramda中映射和缩减是使用循环实现的。

编辑

如果您的结构实际上不是数组，而是类似于链接列表，则需要通过检查是否为单例空元素来检查是否处于末尾。这里有一个使用reduce实现单向链表的示例，它看起来像本答案中的先前访问器和停止条件：

function List() {}

List.prototype.cons = function(a) {
  var c = new List();
  c.a = a;
  c.d = this;
  return c;
}

List.prototype.car = function() {
  return this.a;
}

List.prototype.cdr = function() {
  return this.d;
}

List.prototype.reduce = function(proc, init) {
  function helper (lst, acc) {
    return lst === emptyList ? 
           acc :
           helper(lst.cdr(), proc(acc, lst.car()));
  }
  return helper(this, init);
}

List.prototype.length = function() {
  return this.reduce(acc => acc+1, 0);
}

List.prototype.reverse = function() {
  return this.reduce((acc, a) => acc.cons(a),emptyList);
}

// Singleton empty list
window.emptyList = new List();

var example = emptyList.cons(1).cons(2).cons(9);
example.reduce((a,e)=>a+e,0); //=> 12
example.length(); // ==> 3
example.reverse(); // ==> (1,2,9)

- Sylwester

---

这将返回数组项的总和，而不是数组的长度。在没有预先知道数组长度的情况下用于退出条件，是否可能使用这种递归形式？（我最终在 Lua 的一个版本中玩耍，通常可以使用这种形式通过可变计数变量确定数组长度：https://dev59.com/7HE85IYBdhLWcg3wl0jF） - user479947

对于数组，长度总是已知的，因此通过遍历来查找该值始终会使用长度。对于像单向链表这样的结构，长度不是一个容易的属性，因为您可以通过在前面添加新元素来增加长度。请参见示例进行比较。 - Sylwester

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - user479947

Answer 5

你可以不使用任何for循环来实现这个。

function arrLen(array, length=0) {
    if (array[0] === undefined) return length;
    length++;
    const newArray = array.slice(1);
    return arrLen(newArray, length)
}

var a = ["a", "b", "c", "d"];
var lengthOfA = arrLen(a);

首先，我试图得到基本情况。一旦递归发现在数组中没有元素，则递归将停止工作。当我的数组中没有元素时，array[0] === undefined。我已将长度初始化为零，以便可以在每次迭代后增加长度值，我使用 length++ 完成了这项工作。我的另一个目标是在每次迭代后从数组中删除第一个元素，这就是我使用切片方法的原因。然后，在返回的函数中使用这些新的数组和长度值。

- Mithhu