Javascript递归计数

Question

我申请了一份被赋予这项任务的工作。我必须编写一个函数 reversePrint()，它返回一个反向数组，其中包含传递对象的值。

这是对象

var someList = {
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3,
            next: {
                value: 4,
                next: null
            }
        }
    }
};

我的尝试

function reversePrint(linkedList) {
  // empty array with the result
  var b = [];
  // while loop to check if current next is not null
  while ( linkedList.next !== null ) {
    // push current value into the array
    b.push(linkedList.value);
    // go one level deeper
    linkedList = linkedList.next;
  }
  // push the last value into the array
  b.push(linkedList.value);
  // return reversed array
  return b.reverse();
}

该功能有效，但我觉得有更好的方法来做到这一点。我已经在 stackoverflow 中搜索了 javascript 递归操作，但找不到任何被认为是重复的东西。有没有更有效的方法来做到这一点？

Answer 1

您的代码从根本上没有错，但您的直觉是正确的:递归解决方案似乎更符合数据结构的递归性质，会更简洁，而且可以编写成避免相反的情况。

var someList = {value: 1, next: {
    value: 2, next: {
        value: 3, next: {
            value: 4, next: null}}}};

function reversePrint(input) {
  return !input ? [] : reversePrint(input.next).concat(input.value); 
}

console.log(reversePrint(someList));

请注意，此解决方案不可进行尾部优化，如果输入可能非常深，最好避免使用。尾部可优化的解决方案是:

function reversePrint(input) {
  return function inner(input) {
    return !input ? [] : [input.value].concat(inner(input.next));
  }(input).reverse();
}

当然，使用迭代解决方案避免反转是可能的，但它需要在每一步都将代价高昂的 unshift 移到数组的前面。另一方面，递归解决方案创建了多个长度逐渐增加的数组，这也不是很便宜。