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)