JavaScript: Recursive function used to find a Linked list node returns wrong node

Question

In an attempt to understand recursion better, I've decided to try a recursive function to find an item in a linked list instead of a while loop.

Near the end, my recursive function seems to be doing the right thing by returning the correct node, but then it runs return a few more times unexpectedly (I don't know why) and returns an incorrect object. Am I missing something?

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

georg · Accepted Answer · 2016-02-05 13:04:09Z

7

Your function should be like this:

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

This is the general pattern:

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)

edited Feb 5, 2016 at 13:04

answered Feb 5, 2016 at 12:34

georg

216k57 gold badges324 silver badges401 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

NaCl · Accepted Answer · 2016-02-05 12:35:14Z

3

You should catch the return value of the recursive function inside the if.

Just do

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

And it works as expected.

answered Feb 5, 2016 at 12:35

NaCl

2,7333 gold badges26 silver badges38 bronze badges

2 Comments

hzhu Over a year ago

Sorry, could you explain what catching the return value inside the if does? I'm still not understanding the bug. Is it the same as returning something inside the if? But it works!

NaCl Over a year ago

getItem returns each time the current element, however, in your current code you omit that and thus you return list again.

RPichioli · Accepted Answer · 2016-02-05 13:39:33Z

2

The point is that you are creating the "item" variable inside the iteration. When you go to the next call you lost the value of the parent process because eu are registering it again, so you have to create it outside the function and use the reference inside. Look:

// 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"

edited Feb 5, 2016 at 13:39

answered Feb 5, 2016 at 12:52

RPichioli

3,3553 gold badges27 silver badges31 bronze badges

Collectives™ on Stack Overflow

JavaScript: Recursive function used to find a Linked list node returns wrong node

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related