Saving count variable through recursion with only 1 argument

Question

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:

should be invoked with one argument
should use recursion by calling itself

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

#9 from github.com/JS-Challenges/recursion-prompts/blob/master/src/… — tbd_
– tbd_, Commented Jul 22, 2019 at 0:39

Mark · Accepted Answer · 2019-07-22 21:21:16Z

1

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.

edited Jul 22, 2019 at 21:21

answered Jul 22, 2019 at 0:53

Mark

92.7k8 gold badges116 silver badges156 bronze badges

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

Comments

CertainPerformance · Accepted Answer · 2019-07-22 00:46:31Z

0

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'));

answered Jul 22, 2019 at 0:46

CertainPerformance

373k55 gold badges354 silver badges359 bronze badges

Comments

Scott Sauyet · Accepted Answer · 2019-07-22 13:12:26Z

0

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.

answered Jul 22, 2019 at 13:12

Scott Sauyet

50.9k5 gold badges57 silver badges111 bronze badges

Comments

Mulan · Accepted Answer · 2019-07-22 21:33:46Z

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

Collectives™ on Stack Overflow

Saving count variable through recursion with only 1 argument

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related