如何解决这个Javascript递归问题找到字母在数组中出现的次数

Question

我知道return语句有问题，但是我不知道是什么。

let arr = ['a', 'b', 'c', 'a']
let size = arr.length - 1
let counter = 0
function findOcc(arr, size, x) {
if (size === 0) {
return counter
} else {
if (arr[size] === x) return counter++
findOcc(arr, size - 1, 'a')
}
}
console.log(findOcc(arr, size, "a"))

Answer 1

一个更简单的递归版本使用数组解构来根据目标值测试第一个值，如果匹配则加1，如果不匹配则加0，然后在数组的其余部分循环。当值未定义时停止，这意味着数组中的元素已用完。

const countOcc = (target) => ([x, ...xs]) =>
x == undefined ? 0 : (x == target ? 1 : 0) + countOcc (target) (xs)
const arr = ['a', 'b', 'c', 'a']
console .log (countOcc ('a') (arr))
console .log (countOcc ('b') (arr))
console .log (countOcc ('c') (arr))
console .log (countOcc ('d') (arr))

虽然我们可以改变这一点，使其尾部递归，目前的JS引擎仍然不做尾部调用优化，所以它似乎有点毫无意义。如果要对大型数组执行此操作，则可能需要用迭代来代替递归进行重写。

Answer 2

似乎你的逻辑是正确的，但没有很好地实现它。

• 对于基本条件，你说if (size===0)返回计数器。这意味着你只是返回计数器，但arr[0]是有效的支票。所以当你检查元素时你真正想要的是在下一行arr[size-1]即else

• 对于else条件，您打算增加计数器，这是正确的，但您不应该返回。而是返回下一次调用size-1

  的值。

• 你的尺寸声明应该是let size = arr.length

• 最后一个参数应该是x而不是a。

代码是:

let arr = ['a', 'b', 'c', 'a']
let size = arr.length
let counter = 0
function findOcc(arr,size,x) {
if (size === 0) return counter
if(arr[size-1]===x)  ++counter
return findOcc(arr,size-1,x)
}
console.log(findOcc(arr, size, "a"))

Answer 3

如果可以更改原始数组，则可以将函数简化如下:

const origArr = ['a', 'b', 'c', 'a'];
// a simpler implementation of the same recursive function
function findOcc(arr, x) {
return (
arr.length                // if "arr" length is 1 or more
? arr.pop() === x         // ".pop()" the last elt & compare with "x"
? 1 + findOcc(arr, x)   // add 1 & recurse using the shorted/mutated "arr"
: findOcc(arr, x)       // do not add 1, but recurse using the mutate "arr"
: 0                       // no more elements in "arr", so return 0
)
}
// using "..." spread to avoid "arr" from being changed
console.log('number of times "a" occurs is: ', findOcc([...origArr], "a"))
console.log(
`"d" occurs in ["${origArr.join('", "')}"] ${findOcc([...origArr], "d")} times...`
)