javascript - 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.