我可以在递归问题中使用其他参数吗? [英] Can I use additional parameters in recursion problems?

问题描述

好的，我在一家公司接受面试，面试官问我递归问题.这是一次在线面试，因此，他在CodeSandbox(在线代码编辑器/协作工具)上设置了问题说明和功能签名.我应该填写功能主体.他在函数签名中只有一个参数.我添加了另一个参数只是为了跟踪结果.他说我不应该添加另一个参数(我正在向其他参数提供默认值)，因为它会更改函数签名.

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.

解决方案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
}

在上述解决方案中，我添加了一个可选参数: index 来跟踪要匹配的索引.这里的问题是，添加此可选参数是否合理?

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?

解决方案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.

现在，我再次重复这个问题，解决方案1是否被视为无效解决方案?

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

推荐答案

每当您向签名添加默认参数时，都有潜在的缺陷.正如其他人指出的那样，用户可以使用他们选择的任何值来调用它.

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.

使用解决方案1，致电

isPalindrome ('levee', 1)

将产生 true ，因为您忽略了第一个和最后一个字母.

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

更糟糕的是，

isPalindrome ('madam', 4)

会重复出现，直到堆栈空间用完，调用 isPalindrome('madam'，5)，这将调用 isPalindrome('madam'，6)，依此类推

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]

符合预期.

通常，当我们有 [...] .map(x => foo(x))时，我们可以简单地将其替换为 [...] .map(foo).这是清理代码的好方法.

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.

但是这里:

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

将抛出该异常，因为 map 为提供给它的函数，索引和原始数组提供了额外的参数.因此，此调用

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)

它会弄错'levee'/2 并炸毁'madam'/4 .

重点是我们经常使用 map ，好像它只提供我们关心的项目一样.JS允许它及其非常有用.但是，如果我们的函数执行一些带有额外参数的操作，我们就会被它咬住.

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.

这篇关于我可以在递归问题中使用其他参数吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！