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 parameter), as it changes the function signature.

Now, in my opinion, if you are adding an optional parameter 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 parameter: index to keep track of the index to be matched. The question here is that if it's reasonable to add this optional parameter?

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

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

Answer 1

Solution 1 is not valid, because an unexpected signature can fail in unexpected ways. You were given a particular function signature because that's how it's expected to be used.

An example of such an unexpected failure, using Solution 1:

>> ["aba", "aba"].map(isPalindrome)
== Array [ true, true ]
>> ["aba", "aba", "aba"].map(isPalindrome)
Uncaught InternalError: too much recursion

This occurs because map does use the additional arguments: the second is the index in the array.

Solution 2 does not fail like this, because it maintains the original signature and ignores the additional arguments.

This can be worked around, such as by calling isPalindrome wrapped in another function like .map(value => isPalindrome(value)), but the point is that having been given a particular signature indicates it's meant to be used in a particular way, and without knowing what that way is, you just can't really say it makes no difference.

Answer 2

It is often necessary to introduce additional parameters when turning an iterative solution into a recursive, especially into a tail-recursive one.

The reason is that the implicit state that the iterative version has must go somewhere and the only place it can go is on the call stack … either in the return value or parameters.

The way this is usually done is the same way we hide implementation details in any other case: by introducing a private implementation. In languages which support nested functions, the standard way is to introduce a nested helper function like this:

function isPalindrome(input) {
    if (input.length <= 1) {
        return true;
    }

    return isPalindromeRec();

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

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

        if (isAMatch) {
            return isPalindromeRec(++index)
        }

        return isAMatch
    }
}

Answer 3

Well I like the index solution simply because it doesn't require creating multiple sub strings on the heap.

The problem with interview questions is they're mostly "guess what I'm thinking" games. So while you and I might be fully objectively right about which is the better solution the point is to show that you can work with the interviewer to either get them to see that or figure out what will make them happy even if it is stupid.

But to answer your exact question, no. Solution 1 is still valid. If challenged about the signature all you had to do was call _isPalindrome(input, index) from isPalindrome(input). No one said you couldn't define a new function. You are still using recursion. But can you get the interviewer to see that?

Being right is a small consolation if you don't get the job.

Answer 4

The solution validity is defined by the requirements.

The solution 1 doesn’t comply with the non-functional requirement “do not change the signature”. This has nothing to do with recursion but with your interview conditions.

This being said, and from an SE point of view, both algorithms are not equivalent:

• solution 2 is a tail recursion, which can easily be optimized as a loop by the compiler. It’s moreover a true recursion, that fully solves the problem based on a smaller instance of the same problem.
• solution 1 (edited, see comments) is also tail recursive when closely checking the applicable rules. But it is in reality the solution to a different problem: it’s no longer “is it a palindrome” but “is it a palindrome starting at index ...”. It is certainly a clever adaptation of an iterative solution making it recursive with the iterator as an argument. The trick of the default parameter helps to stay close to the initial requirements. But not only does it not comply with the requirements, but in addition the function could be called with an explicit index beyond the half length or even beyond the bounds, which might produce wrong results.

Answer 5

I see three aspects:

1. Was the extra-argument answer correct?

I feel that would depend on how the question was asked. Were you asked to implement the given function signature, or just to check palindromes using recursion?

While being technically correct is the best kind of correct, it doesn't mean they'll be impressed.

2. How to handle the interview situation?

The interviewer may insist on a given signature for different reasons, for example:

• it was a part of the intended question that they forgot to state, or you didn't hear
• they want to see if you can find another solution
• they don't care about performance
• they don't see the performance advantage of the index version

The first three seem quite likely to me: if they wanted the fastest and easiest way to detecet palindromes, they wouldn't impose restrictions like using recursion.

As I see it, you have two options: do it their way, or convince them of your way.

Convincing them seems risky, as it could only work if the reason they disagree is because missed the performance advantage, you explain it clearly, and their ego doesn't get hurt. You'll have to read the situation.

Solving it their way is less impressive, but safer. Probably the best way to get the job.

3. Is the solution with two arguments good, generally?

Outside this interview context, I would say its about performance vs readability. Adding the index might be more performant, and I would probably prefer it for that reason. But the single-argument version is more readable to me, and would be preferred in languages that have string slices.

Answer 6

I would personally give a problem where recursion is a more natural fit, but if this is what I had to work with, I would prefer solution 2.

The reason is that using an index is relatively rare in recursive algorithms in the wild. They usually overcomplicate things and make the state more difficult to reason about. It's a sign that you first thought of how you would solve this with an imperative loop, then converted it to recursion, rather than thinking about what the subproblem is.

It's also more difficult to tell what your base cases are. Does solution 1 handle an empty string? I can't tell at a glance. The point of exercises like this isn't efficiency, it's clarity. How much effort is it for a reader to tell if it's correct?

Answer 7

There are plenty of situations where there is a function that needs implementing, and a simple implementation uses a recursive function with an additional parameter. For example Quicksort, where the original function has one argument (an array, assuming it is possible to determine the number of array elements), and then you call a recursive function with the index of the first and last element of a sub array as arguments. That recursive function is likely invisible to the original caller.

Answer 8

I assume that the question was asked to see if you can apply functional reasoning. Technically, both solutions are recursive.

Solution 1 looks a lot like an iterative solution. The next “iteration” is done by calling the function (recursively) with an incremented index.

Solution 2 shows functional reasoning. It is the commonly accepted way to do recursion. Usually, proper recursion can have additional parameters that carry intermediate states. It is, however, highly uncommon to add a counter as parameter.

To the interviewer you insisting that solution 1 is an elegant solution might show (whether true or not) that you have a narrow set of tools for problem solving. Asking for recursion gives you the possibility to show that you know some functional way to solve problems. You showing an iterative solution might come off as ignorant to the power and elegance recursive functions might provide in contrast to loops.

There is a saying in programming: “If the only tool you have is a hammer, everything looks like a nail.” You could have showed that you also have a screwdriver ;-)