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?

• Doc Brown: When the task is to write a function with a given signature, you should write a function with that given signature. And if the task is to write a correct function (and not a fast function) I would prefer an implementation for which it can be easier seen it is correct or not. Your solution 2 looks way simpler, and I can immediately spot that you missed to handle the case "str.len==0" correctly, so I would prefer that as a first shot (but with a correction for the missing case, of course).
• Vaelus: Solution 1 infinitely recurses given an empty string as input. Also if index >= str.length
• Jörg W Mittag: @Vaelus: And the latter is precisely why the index parameter should be private and not be exposed to the caller.
• xehpuk: Next time, use arguments[1]. 😉
• tpb261: The question title should have been: Is it wrong to change the function signature from what was given by the interviewer? And to answer you question you could have written a different function the way you wanted and called it from the "original".

Answer 1

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.

• JounceCracklePop: Downvoted because in many systems, most public methods are implemented to an interface, and interfaces must be written based on what their consumers need to do, not what their implementations would like. You are acting like the exact signature is a minor detail and you need to convince the interviewer of this, but it's very much not. In fact thinking it's OK to change the signature when implementing an interface is a common error I see in junior programmers and signifies they don't fully understand what they're doing yet.
• JounceCracklePop: @candied_orange write it again. "I like the solution"; "get them to see that [it's right] or [do it stupid]", "Solution 1 is still valid"; "[do it the stupid way] if challenged"; "being right [by changing the signature] is a small consolation". You are very clearly saying that changing the signature is OK and even "right", when it's very much not OK and very much wrong.
• JounceCracklePop: @candied_orange Yes. If your interface specifies the one-argument signature then it literally does not even compile. Even if you're not implementing an interface, you're leaking implementation details to the caller. The caller should never be allowed to specify a different value. Izkata showed how this can unexpectedly break things in another answer.
• Alexei Levenkov: @candied_orange to me your answer reads as "interviewers are generally clueless about what they are asking and this is completely pointless restriction to not allow to add extra default parameter, here is a hack to give that @#$# what they want" (which may be a reason why OP accepted the answer). I'm not trying to argue much here, it is likely my bias (as I've been on interviewer's side of the conversation more often) rather than post itself.
• Frax: -1. There is a huge difference between "this is a correct solution" and "you can easily explain how to make a correct solution out of it". The interviewer was correct to insist that the solution changes the signature, and the OP was wrong to say that it doesn't matter. I'd expect the interviewer to accept the explanation like "well, we can add a simple wrapper to have the exact signature we need, let's not waste time on writing it explicitly", but OP clearly insisted on the default argument making no difference at all.

Answer 2

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.

• Brian: In addition to behavioral changes like the one you describe above, exposing internal parameters in the signature also tends to confuse consumers of the function; such parameters are often exposed to the programmer by their IDE.
• Carson Graham: using array.map(someFunction) is javascript is generally an antipattern - and should not be used. For example, ["1","2","3"].map(parseInt) returns [1, NaN, NaN].
• Carson Graham: Thinking about it, the parseInt function is really similar to the isPalindrome function as it takes in an optional parameter with a default value as the second argument. Despite the "unusual" behavior when using map, parseInt is still part of the standard library. In addition, map passes 3 parameters, not 2, which while you didn't touch on it in your answer, if you're going to pass a function like that you need to know and have the number of arguments memorized.
• ruakh: @CarsonGraham: Would you avoid array.map(someFunction) even if someFunction is documented to be usable that way?
• Sulthan: @CarsonGraham No, that's not an antipattern. The real problem is that the javascript standard library is full of antipatterns and nasty surprises.

Answer 3

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
 }
}

• Owen Reynolds: And even without nested functions, a well-known trick is a driver function supplying the extra parameters to the real one: isPalind(string w) { return _isPalind(w,0); }
• IMil: while agreeing with your approach in general, I'd change it a bit: use two parameters in the internal function, startIndex and endIndex. This would remove the need to a complicated call to Math.floor, making the stop condition simply startIndex >= endIndex
• David Hammen: You can easily change the inner function so that it both eliminates the local variable isAMatch and is tail recursive.
• Jörg W Mittag: @IMil: I tried to keep the code as close to the OP's as possible, only demonstrating how you can use auxiliary functions to hide the change in signature.
• Jörg W Mittag: @DavidHammen: I tried to keep the code as close to the OP's as possible, only demonstrating how you can use auxiliary functions to hide the change in signature. Note that there is no change required to make it tail recursive. Both my version and the OP's original version already are.

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.

• candied_orange: While I admire the skill of spotting tail recursion, keep in mind that in many development stacks it's just an academic exercise. Not everybody supports it.
• Theodore Norvell: Solution 1 is also tail recursive and does not use backtracking.
• David Hammen: @Christophe - There is no backtracking in solution 1. There's a big difference between non-tail recursive algorithms and backtracking algorithms. Moreover some languages / some implementations do not optimize for tail recursion. As of January 1, 2020 Safari was the only browser that supports tail call optimization for javascript.
• Bernhard Barker: Why do you say one is tail recursive and the other is not? Both end with if (condition) return isPalindrome(...); else return false;. There doesn't seem to be any structural difference there. But, even if there were this difference, you'd have a hard time convincing me that the tail-recursive solution which involves creating a copy of the string at every step would be more efficient than just passing around the index.
• Theodore Norvell: @DavidHammen The only recursive call in solution 1 is return isPalindrome(...). It's a recursive call followed immediately by a return. So, yes, it is tail recursive as written.

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.

• cmaster - reinstate monica: This should be the accepted answer. Pity that you were late to the party...

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?

• rghome: I don't agree that using an index is uncommon. I use that technique frequently. It is pretty much mandatory with text or array processing if you want to avoid creating a lot of object copies.
• Karl Bielefeldt: Admittedly, favoring performance over clarity is more common than I would prefer.
• Jasen: copies are only made in languages that don't support slices

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