CODEWITHSUNDEEP
javascriptrecursion
iCodeYouCodeWeAllCode
iCodeYouCodeWeAllCode

Reputation: 55

Understanding recursion of list

I need code that outputs a range of numbers with 2 given inputs. However, I don't understand how we can push to list when list = range(start_num, end_num - 1). An array is only defined in the if statement. How does it work?

var range = function(start_num, end_num) 
{
  if (end_num - start_num === 2) 
  {
    return [start_num + 1];
  } 
  else 
  {
    var list = range(start_num, end_num - 1);
    list.push(end_num - 1);
    return list;
  }
};

console.log(range(2,9));

Upvotes: 1

Views: 61

Answers (1)

Miguel
Miguel

Reputation: 20633

Maybe it helps to visualize it step by step:

// Original function
function range(start_num, end_num) {
  if (end_num - start_num === 2) {
    return [start_num + 1];
  } else {
    var list = range(start_num, end_num - 1);
    list.push(end_num - 1);
    return list;
  }
}

console.log(range(2, 9)); // [3, 4, 5, 6, 7, 8]

//---------------------------------------------
// Step by step

// step 1
function range(2, 9) {
  if (7 === 2) { // false
    return [3];
  } else {
    var list = range(2, 8); // result of step 2 which is [3, 4, 5, 6, 7]
    list.push(8);
    return list; // returns [3, 4, 5, 6, 7, 8]
  }
}

// step 2
function range(2, 8) {
  if (6 === 2) { // false
    return [3];
  } else {
    var list = range(2, 7); // result of step 3 which is [3, 4, 5, 6] 
    list.push(7);
    return list; // returns [3, 4, 5, 6, 7]
  }
}

// step 3
function range(2, 7) {
  if (5 === 2) { // false
    return [3];
  } else {
    var list = range(2, 6); // result of step 4 which is [3, 4, 5]    
    list.push(6);
    return list; // returns [3, 4, 5, 6]
  }
}

// step 4
function range(2, 6) {
  if (4 === 2) { // false
    return [3];
  } else {
    var list = range(2, 5); // result of step 5 which is [3, 4]
    list.push(5);
    return list; // returns [3, 4, 5]
  }
}

// step 5
function range(2, 5) {
  if (3 === 2) { // false
    return [3];
  } else {
    var list = range(2, 4); // result of step 6 which is [3]      
    list.push(4);
    return list; // returns [3, 4]
  }
}

// step 6
function range(2, 4) {
  if (2 === 2) { // true
    return [3]; // return [3]
  } else {
    // ...
  }
}

The stack sort of looks like this:

step 1: I call range ↴
  step 2: I call range ↴
    step 3: I call range ↴
      step 4: I call range ↴
        step 5: I calls range ↴
          ↲ step 6: OK so I do not call range, return my value
        ↲ step 5 OK return step 6 result 
      ↲ step 4 OK return step 5 result
    ↲ step 3 OK return step 4 result
  ↲ step 2 OK return step 3 result
↲ step 1 OK return step 2 result

Upvotes: 2

Related Questions