CODEWITHSUNDEEP
javascriptrecursion
tbd_
tbd_

Reputation: 1268

Saving count variable through recursion with only 1 argument

What's the best way to "save" the returned variable from the previous stack all the way to the first call using only one argument?

I know of 2 techniques to 'save' variables in recursion, but the test cases don't let me implement them that way.

Prompt: reverse a string using recursion.

Test cases:

Attempt 1 (using helper function):

var reverse = function(string) {
 var str = string.split('');
 var reversed = [];
 var helper = function(i) {
   reversed.unshift(str[i]);
   if (i < str.length) {
     i++;
     helper(i);
   }
 };
 helper(0);
 return reversed.join('');
}

Attempt 2 (without helper + using extra arguments)

var reverse = function(string, index, prev) {
  var prev = prev || [];
  index = index || 0;

  if (index < string.length) {
    prev.unshift(string[index]);
    index++;
    reverse(string, index, prev);
  }

  return prev.join('');
};

What would be the 3rd way of doing this? Thanks!

Source: #9 from https://github.com/JS-Challenges/recursion-prompts/blob/master/src/recursion.js

Upvotes: 2

Views: 1149

Answers (4)

Mulan
Mulan

Reputation: 135357

Here's another way you can do it using destructuing assignment and a technique called continuation-passing style -

const cont = x =>
  k => k (x)

const Empty =
  Symbol ()

const reverse = ([ s = Empty, ...more ]) =>
  s === Empty
    ? cont ("")
    : reverse
        (more)
        (rev => cont (rev + s))

reverse ("hello world") (console.log)
// dlrow olleh

But watch out for really big strings -

const bigString =
  "abcdefghij" .repeat (1000)

reverse (bigString) (console.log)
// RangeError: Maximum call stack size exceeded

Here's another technique called a trampoline which allows to think about the problem recursively but have a program that is both fast and stack-safe. Have your cake and eat it, too -

const recur = (...values) =>
  ({ recur, values })

const loop = f =>
{ let r = f ()
  while (r && r.recur === recur)
    r = f (...r.values)
  return r
}

const reverse = (s = "") =>
  loop   // begin loop ...
    ( ( r = ""    // state variable, result
      , i = 0     // state variable, index
      ) =>
        i >= s.length  // terminating condition
          ? r          // return result
          : recur      // otherwise recur with ...
              ( s[i] + r  // next result
              , i + 1     // next index
              )
    )
   
const bigString =
  "abcdefghij" .repeat (1000)

console .log (reverse (bigString))
// jihgfedcba...jihgfedcba

Upvotes: 0

Mark
Mark

Reputation: 92450

You don't need to save anything. If you order the return correctly the call stack will unwind and create the reversed string for you:

var reverse = function(string) {
  if (string.length == 0) return string        // base case
  return reverse(string.slice(1)) + string[0]  // recur 
};

console.log(reverse("hello"))

By returning the result of the recursion before the first character you wind and unwind the stack before the first call returns. You can then get result without maintaining any state other than the call stack.

Upvotes: 1

Scott Sauyet
Scott Sauyet

Reputation: 50807

Others have shown better ways to write your reverse recursively.

But as to the actual question you asked, modern JS allows for default arguments. I tend not to use them very much, but they are very useful in JS to allow you to write this sort of recursion without helper functions. Thus,

const reverse = (string, index = 0, prev = [])  => {
  if (index < string.length) {
    prev .unshift (string [index])
    reverse (string, index + 1, prev)
  }

  return prev .join ('')
}
  
console .log (
  reverse ('abcde')
)

Again, other answers have better versions of reverse. But this should show you how you can have a function that takes only one public variable and yet still uses its extra arguments.

Upvotes: 0

CertainPerformance
CertainPerformance

Reputation: 370989

I'd store the information to be used later in the function body only, without passing it down the call chain:

var reverse = function(string) {
  const { length } = string;
  return string[length - 1] + (
    string.length === 1
    ? ''
    : reverse(string.slice(0, length - 1))
  );
};


var reverse = function(string) {
  const { length } = string;
  return string[length - 1] + (
    string.length === 1
    ? ''
    : reverse(string.slice(0, length - 1))
  );
};

console.log(reverse('foo bar'));

Upvotes: 0

Related Questions