为什么这个“雄辩的Javascript”递归解决方案起作用？

Question

我正在使用Eloquent Javascript，该练习要求找到一种递归解决方案，以在这种形式的嵌套列表中找到第n个元素；

var list = {
   value: 1, 
   rest: {
     value: 2, 
     rest: {
       value: 3,
       rest: null
     }
   }
};

在将我的头挠得太久之后，我适当地检查了答案。

function nth(list, n) {
  if (!list)
    return undefined;
  else if (n == 0)
    return list.value;
  else
    return nth(list.rest, n - 1);

我可以看到这确实产生了正确的结果，但是我不明白为什么。

我对逻辑的理解如下

如果未提供列表或列表为假，则返回undefined，否则，如果n为0，则返回列表的第一个元素-由list.value给出。否则再次调用该函数，但将n减1。

很明显，我必须缺少某些内容，但我不了解此逻辑如何返回第n个元素。似乎它将继续递归直到n == 0。此时，它将仅返回列表的第一个元素。

Answer 1

这是典型的功能样式链接列表迭代。请注意，递归调用继续在list.rest上进行，而不是再次在list上进行。 list.rest是从下一个元素开始的列表。在过程样式中，等同于使用列表的其余部分将是增加索引指针。

这种风格的优点是您在代码中描述了列表的属性：列表L的第n个元素也是从L头开始的列表的第（n-1）个元素。接近声明式表格有时可以使验证所写内容的正确性更加容易。

这种样式的缺点是在列表很大的情况下出现，在这种情况下，这种功能会进行深度递归，而Javascript引擎很可能无法处理。专用于功能语言的编译器/解释器将尽可能消除该递归，将其转换为循环，这种转换称为“尾部调用优化”。 TCO使开发人员摆脱了绑定到堆栈时的束缚，允许功能语言使用递归作为迭代的主要方式，因此在该世界中，您到处都能看到并编写这样的构造。

Answer 2

此声明也使我思考得很好。我终于弄清楚了，所以我觉得我应该补充上一个答案。

nth（list.rest，n-1）中的“ n-1”语句本质上是确定程序何时终止的计时器。请记住，当它变为0时，它将按照此语句返回值。

 else if (n == 0)
    return list.value;

例如，一个列表被传递到您的函数中“ {值：1，休息：{值：2，休息：{值：3，休息：空}}}”您传入2作为参数。它调用该函数并通过if语句，然后进入递归语句。它将调用List.Rest，然后将传入参数的值减小1。它重复上述循环，并到达递归函数，现在传递的参数是List.Rest.Rest，您的参数再次减小1并变为0。当它通过if和else if语句时，由于参数现在为0，因此以下行被触发

else if (n == 0)
    return list.value;

然后返回列表。值...。请记住，您的列表现在是list.Rest.Rest让您现在变得有价值3。