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

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

• javascript
• function
• recursion
• linked-list

Share Improve this question Follow asked Feb 5, 2016 at 12:30 hzhuhzhu 3,79966 gold badges3030 silver badges3939 bronze badges

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 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)

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.

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"