JavaScript：用於查找鏈接列表節點的遞歸函數返回錯誤的節點

爲了更好地理解遞歸，我決定嘗試使用遞歸函數來查找鏈接列表中的項目而不是while循環。JavaScript：用於查找鏈接列表節點的遞歸函數返回錯誤的節點

接近尾聲時，我的遞歸函數似乎通過返回正確的節點來做正確的事情，但它運行時會意外返回多次（我不知道爲什麼）並返回一個不正確的對象。我錯過了什麼嗎？

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

來源

2016-02-05 Henry Zhu

你的功能應該是這樣的：

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)

來源

2016-02-05 12:34:39 georg

你應該抓住，如果裏面的遞歸函數的返回值。

只是做

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

而且它按預期工作。

來源

2016-02-05 12:35:14 NaCl

對不起，你能解釋一下抓住裏面的'if'不返回值？我仍然不瞭解這個錯誤。是否與在'if'中返回內容相同？但它的作品！ –

'getItem'每次返回當前元素，但是，在您當前的代碼中，您會忽略該元素，因此您會再次返回'list'。 – NaCl

問題是你在迭代中創建了「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"

來源

2016-02-05 12:52:37 RPichioli

JavaScript：用於查找鏈接列表節點的遞歸函數返回錯誤的節點

回答

相關問題