关于勒让德公式和递归的问题？

Question

我目前正在学习勒让德公式。到目前为止，我能够使用以下方法解决算法：

const legendre = (p,n,res=0) => Array.from({length:n},(_,i) => res+=Math.floor(n/p**++i)) && res;

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

然而，我就是无法完全克服递归的困难。这是我目前所拥有的：

const legendre = (p,n,i=1,res=0) => p > n ? res : res + legendre(p**i,n,i+1,Math.floor(n/p**i))

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 99 
console.log(legendre(3,60)); // 26
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 300

如您所见，大部分结果都不正确。我在正确的轨道上吗？有人可以给我指出正确的方向或告诉我我做错了什么吗？任何反馈将不胜感激。提前万分感谢:)

Answer 1

我首先将您的第一个代码转换为普通函数：

const legendre = (p, n) => {
  let res = 0;
  for (let i = 1; i <= n; i++) {
    res += Math.floor(n/p**i);
  }
  return res;
}

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

并将其转换为递归函数：

const legendre = (p, n, i=1, res=0) => {
  // base case -> done
  if (i > n) return res + Math.floor(n/p**i);
  return legendre(p, n, i+1, res + Math.floor(n/p**i));
}

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

并且可以像这样制作成单行衬里：

const legendre = (p,n,i=1,res=0) => i > n ? res + Math.floor(n/p**i) : legendre(p,n,i+1,res +Math.floor(n/p**i))

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

我没有研究过这个算法，这些答案只是基于你的第一个代码片段和你的测试用例。

关于勒让德公式和递归的问题？

Question regarding Legendre's formula and recursion?

javascript

algorithm

recursion

ecmascript-6