Can I use additional parameters in recursion problems?

Question

Okay, I was being interviewed at a company and the interviewer asked me a recursion problem. It was an online interview, so, he had set up the problem statement and a function signature on CodeSandbox(an online code editor/collaboration tool). I was supposed to fill-up the function body. He had only one parameter in the function signature. I added another parameter just to keep track of the result. He said I shouldn't add another parameter(I was providing a default value to the additional param), as it changes the function signature.

Now, in my opinion, if you are adding an optional param to the signature, it wouldn't make any difference. Let me take a simple example to make it more clear to you:

Problem: Check if the input is a palindrome.

Solution 1:

function isPalindrome(input, index = 0){
    const isAMatch = input[index] === input[input.length - 1 - index]

    if (index === Math.floor((input.length - 1) / 2)) {
        return isAMatch
    }

    if (isAMatch) {
        return isPalindrome(input, ++index)
    }

    return isAMatch
}

In the solution above, I added an optional param: index to keep track of the index to be matched. The question here is that if it's reasonable to add this optional param?

Solution 2:

function isPalindrome(str){
    if(str.length === 1) return true;
    if(str.length === 2) return str[0] === str[1];
    if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1))
    return false;
}

In this solution, we aren't using any additional param.

Now I'm repeating the question again, would the Solution 1 be considered as invalid solution?

Answer 1

There is a potential flaw whenever you add default parameters to signatures. As others have pointed out, users could call it with whatever values they chose.

With solution 1, calling

isPalindrome ('levee', 1)

will yield true, since you ignored the first and last letter.

Even worse,

isPalindrome ('madam', 4)

will recur until you run out of stack space, calling isPalindrome ('madam', 5), which will call isPalindrome ('madam', 6), etc.

While you can document this to try to ensure that users don't do this in a stupid way, it's quite possible that they wouldn't even know that they're doing it.

['kayak', 'level', 'levee', 'nonpalindrome', 'madam'] .map (s => isPalindrome(s))
//=> [true, true, false, false, true]

as expected.

Usually when we have [...] .map (x => foo (x)), we can simply replace it with [ ... ] .map (foo). It's a nice way to clean up the code.

But here:

['kayak', 'level', 'levee', 'nonpalindrome', 'madam'] .map (isPalindrome)

will throw that exception, because map supplies extra parameters to the function supplied to it, the index and the original array. Thus this calls

isPalindrome('kayak', 0)
isPalindrome('level', 1)
isPalindrome('levee', 2)
isPalindrome('nonpalindrome', 3)
isPalindrome('madam', 4)

and it would get 'levee'/2 wrong and blow up on 'madam'/4.

The point is that we often use map as though it supplies only the item we care about. JS allow this and its very useful. But we can be bitten by it if our function does something with extra parameters.

There are various ways to resolve this. The simplest, of course, is to ignore it. Caveat emptor. But you never know when this might come back to bite you. If this is an internal function not meant to be used by anyone else, this might be fine. But as a function used by others, it might be a problem.

A second technique would be simply to add a wrapper function. Your recursive function with its helper variables becomes an internal function, not exposed to the world, and you write a wrapper function that calls it the way you choose. You can then default these helpers or pass them from the wrapper. Thus

function _isPalindrome(input, index) {
// ... recursive implementation here
}

function isPalindrome(input) {
  return _isPalindrome(input, 0)
}

This is a general solution to the issue. I use this for public recursive functions that need helper variables. For internal ones I often write as you did. But even then problems like this occasionally trip me up.

Answer 2

Use a helper method that has whatever parameters that you want, if you intend to get full credit on the question.

Typically, an interview question like this one reflects the real job, inasmuch as professional developers spend a lot of time implementing interfaces over which they have no control. Experts can work with those restrictions by implementing whatever they need using additional methods or classes without changing the public interface. The questioner wants to know if you're that kind of expert.

Answer 3

There is nothing wrong if the language allows you to do that. It's just that interviewer wanted you to think for the solution no 2.

Solution 1 is as correct as solution no2.

Infect in some cases, we have to pass some additional arguments to differentiate is this the main entry or recursive entry.

So long story short, both of your answers are equally correct.

Answer 4

Solution 1 is Correct!

But, you can try it!

function reverseString(str) {
  if (str.length === 1) {
    return str;
  }
  return reverseString(str.slice(1)) + str[0];
}

function isPalindrome(str) {
  return str === reverseString(str);
};

console.log(isPalindrome('12345678987654321'))

Answer 5

I agree that both the answers are correct and I as an interviewer will provide full credits to you.

But if you don't want to do Array.slice() and still continue with the first solution, which in my opinion is much cleaner, then I'd rather consider this technique, to satisfy the interviewer. But again, your answers are absolutely correct.

function isPalindrome(input){
let index = [...arguments][1] || 0; // this part is changed
print(index)
const isAMatch = input[index] === input[input.length - 1 - index]

if (index === Math.floor((input.length - 1) / 2)) {
    return isAMatch
}

if (isAMatch) {
    return isPalindrome(input, ++index)
}

return isAMatch;

}

Answer 6

The interviewer may think , a caller can manipulate your method with invalid data. Example

isPalindrome("welcome", 2) 

The argument is users choice they have full freedom to pass any value. But if you are a solution provider you should validate the input. Consider all input as evil.

Answer 7

I'm still finding interesting ways to represent recursive programs that are flexible and stack-safe. In another answer from this year, I show a way to make any recursive program stack-safe without having to "rethink" the entire function to use a stack or queue.

In this example program below, we implement a lighter solution that is still very powerful. Our program is expressed recursively however the evolved process is an iterative one. We compute the 100,000th fibonacci number in less than one second. The result is over 20,000 digits long.

Loop and Recur, introduced here, are sufficiently generic to represent many tail-recursive programs -

const fib = x =>
  Loop                              // <- loop
    ( (n, a, b) =>                  // <- vars "n", "a", and "b"
        n <= 0n                     // <- exit condition
          ? String(a)               // <- base case
          : Recur(n - 1n, b, a + b) // <- recursive case
    , BigInt(x)                     // <- init "n"
    , 0n                            // <- init "a"
    , 1n                            // <- init "b"
    )
  
function Loop (f, ...init)
{ let r = f(...init)          // <- apply f for initial result
  while (r instanceof Recur)  // <- if result is Recur
    r = f(...r)               // <- apply f again
  return r                    // <- return non-Recur result
}

function Recur (...v)
{ return Object.create                                // <- simple object
    ( Recur.prototype                                 // <- prototype
    , { constructor: { value: Recur }                 // <- constructor
      , [Symbol.iterator]: { value: _ => v.values() } // <- values
      }
    )
}

document.body.textContent = fib(100000)

body { overflow-wrap: anywhere; }