JavaScript:用于查找链表节点的递归函数返回错误的节点

Question

为了更好地理解递归，我决定尝试使用递归函数在链表中查找项目，而不是while循环。

接近尾声时，我的递归函数似乎通过返回正确的节点来做正确的事情，但随后它意外地运行了几次返回（我不知道为什么）并返回了一个不正确的对象。我错过了什么吗？

var linkedList = {
  element: 'head',
  next: {
    element: 'SF',
    next: {
      element: 'LA',
      next: {
        element: 'SD',
        next: {
          element: 'NY',
          next: null
        }
      }
    }
  }
}

function getItem(city, list) {
  var item = list
  if (item.element != city) {
    item = item.next
    getItem(city, item)
  }
  return item
}
console.log( getItem('SD', linkedList ) ) // logs "SF" node but I expect "SD" node

Answer 1

你的函数应该是这样的：

function getItem(city, item) {
  if(item === null)
    return null;
  if (item.element === city)
    return item;
  return getItem(city, item.next)
}

这是一般模式：

find-recursively (predicate, element)
    // terminal condition, failure
    if element is null 
        return null
    // ok, found it
    if element matches predicate
        return element
    // recurse deeper
    return find-recursively (predicate, element.next)

Answer 2

你应该在 if 中捕获递归函数的返回值。

只是做

if (item.element != city) {
    item = item.next
    item = getItem(city, item)
}

它按预期工作。

Answer 3

关键是你在迭代中创建"item"变量。当您转到下一个调用时，您丢失了父进程的值，因为 eu 再次注册它，因此您必须在函数外部创建它并在函数内部使用引用。看：

// Creating the variable
var item = null;
function getItem(city, list) {
  // Working with the value
  item = list;
  if (item.element != city) {
    item = item.next
    getItem(city, item)
  }
  return item
}
console.log( getItem('SD', linkedList ) ) // logs "SF" node but I expect "SD" node
// My log returns "SD"