CODEWITHSUNDEEP
javascriptrecursion
jmancherje
jmancherje

Reputation: 6633

Is my solution recursive? (learning recursion)

I am practicing solving problems with recursion for a class.

I am solving the problems on this site : http://www.w3resource.com/javascript-exercises/javascript-recursion-functions-exercises.php

The question I am referring to is stated : Write a JavaScript program to get the integers in range (x, y). Example : range(2, 9) Expected Output : [3, 4, 5, 6, 7, 8]

Before looking at the solution I came up with this:

var range = function (start, end) {
  var result = [];
  var accumulator = start;

  var accumulate = function () {
    accumulator++;
    if (accumulator === end) {
      return;
    } else {
      result.push(accumulator);
    }
    accumulate();
  };

  accumulate();
  return result;
};

The solution on the site is this:

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;
  }
};

Is my solution technically still recursive? I had a similar answer on a quiz recently and I was told my solution is essentially iterative.

Upvotes: 2

Views: 529

Answers (3)

Jared Dykstra
Jared Dykstra

Reputation: 3626

Is my solution technically still recursive?

Yes. You're using tail recursion; however, since no arguments are being passed to accumulate() I can see why someone may say it's essentially iterative. You could easily replace your recursive call with a loop. Recursive algorithms typically leverage the stack.

Because of Javascript's closures, it is harder to understand the concept of recursion in Javascript compared to other languages like C++ or Java or C#.

To understand recursion, you must first understand recursion. :)

Upvotes: 2

memoselyk
memoselyk

Reputation: 4118

To make your solution recursive, it should return some value and somehow combine the result of the recursive call to form the return value of the original call.

Let me illustrate that with an example, by modifying your solution:

var range = function (start, end) {

  var accumulate = function (accumulator) {
    if (accumulator === end - 1) {
      return [accumulator];  // Stop condition 
    } else {
      // Recursive block
      var result = accumulate(accumulator+1);  // recursive call
      result.unshift(accumulator);  // combine result
      return result
    }
  };

  return accumulate(start);
};

The modified accumulate function will return a one-element list for the stop condition, the simplest case it handles, where accumulator reaches the last value to return.

In the example range(2,9), the stop condition will return [8].

Then in the caller, the recursive block

      var result = accumulate(accumulator+1);
      result.unshift(accumulator);
      return result

will take the list [8], and preprend the current value of accumulator (7), so it'll return [7,8].

...and the caller of accumulator(7), will receive [7,8] and preprend the value 6 to the list, to return [6,7,8].

At the end, the original call to accumulator(2) will generate the expected result [2,3,4,5,6,7,8].

Upvotes: 2

thefourtheye
thefourtheye

Reputation: 239443

Though you use recursion, you have simply written a loop in the form of recursion.

I am going to answer this from the purely academical standpoint. If you want to avoid the intermediate state (result) and use purely functional constructs, I would write it like this

function range(start, end) {
  function recRange(current, end) {
    if (current > end)
      return [];
    return [current].concat(recRange(current + 1, end));
  }
  return recRange(start + 1, end - 1);
}
console.log(range(2, 9));
// [ 3, 4, 5, 6, 7, 8 ]

If you see here, we create a new function within the range function, which recursively creates a new array on every iteration (remember: this is not highly performant code, you can simply use loops and be done with this problem efficiently).

The base condition of the recursion is current < end. Once that is met, the recursion stops and an empty array is returned. In all the levels, a new array with the current value is concatenated with the result of the recursive call. So, the evaluation of the calls are roughly understood like this

[3].concat(recRange(3 + 1, end));
[3].concat([4].concat(recRange(4 + 1, end)));
...

at the end, when the recursion unwinds, the values will be like this

[3].concat([4].concat([5].concat([6].concat([7].concat([8].concat([]))))))
[3].concat([4].concat([5].concat([6].concat([7].concat([8])))))
[3].concat([4].concat([5].concat([6].concat([7, 8]))))
[3].concat([4].concat([5].concat([6, 7, 8])))
[3].concat([4].concat([5, 6, 7, 8]))
[3].concat([4, 5, 6, 7, 8])
[3, 4, 5, 6, 7, 8]

and that will be returned as the result.

Upvotes: 3

Related Questions