JavaScript，一个简单的递归函数

Question

JavaScript，一个简单的递归函数

javascriptrecursion

3

我需要帮助实现一个递归函数。这是我第一次尝试在标准的“阶乘”之外使用递归。

我能够在控制台中获得正确的答案，但我无法弄清楚如何使我的函数识别出它已经产生了正确的答案。

挑战：“编写算法确定一个数字是否为‘快乐数字’。”

一个快乐数字由以下过程定义：从任何正整数开始，用其各个数字的平方和代替该数字，并重复此过程，直到数字等于1（保持不变），或者在不包括1的循环中无限循环。在这个过程中以1结束的数字是快乐数字。”

我的尝试：

let num = 19;

let isHappy = (n) => {

  let sNum = `${n}`;
  let sArray = sNum.split('');
  let nArray = sArray.map(el => Number(el))
  let total = nArray.reduce((acc, curr) => {
  return acc += curr * curr
}, 0);
  if(isHappy(total) === 1) {
    return true
  } else {
   return false
  }
}

isHappy(num)

我已经使用while循环并尝试不同的基本情况测试，但没有成功。任何帮助将不胜感激。

- Hubbleduzz

1

你有一些数字的例子吗？它们是否是快乐的？ - Nina Scholz

抱歉，我忘记添加测试变量（num=19），现在它可以正常工作了。 - Hubbleduzz

1

你需要提供循环检测，即使用一个集合来存储之前尝试过的所有数字。 - Turo

4个回答

3

以下是一种不使用先前已查看数字列表的计算答案的方法。

// This function calculates the next number in the sequence from the current number.
const digitSquareSum = n => {
  let sum = 0;
  let num = n;

  while (num > 0) {
    const rem = num % 10;
    num = (num - rem) / 10;
    sum += rem * rem;
  }

  return sum;
};

// Floyd's hare and tortoise algorithm is used to detect cycles in a sequence.
const floyd = (f, n) => {
  let tortoise = f(n);
  let hare = f(f(n));

  while (hare !== tortoise) {
    tortoise = f(tortoise);
    hare = f(f(hare));
  }

  return hare;
};

// If the number in the cycle is 1 then the number is happy.
const isHappy = n => floyd(digitSquareSum, n) === 1;

console.log(isHappy(1));  // true
console.log(isHappy(19)); // true
console.log(isHappy(4));  // false
console.log(isHappy(22)); // false

与Nina的答案不同，这个解决方案是内存高效的。

- Aadit M Shah

感谢您的帮助，我会努力掌握弗洛伊德算法。 - Hubbleduzz

1

这是@Nina答案的全球缓存版本。

const emotion_unknown = Symbol('emotion_unknown');
const happy_cache = new Map;
happy_cache.set(1, true);

function isHappy(value) {
  if (happy_cache.has(value)) {
    if (happy_cache.get(value) == emotion_unknown) return false
    else return happy_cache.get(value)
  }
  //optional: only set cache for value < 1000 since next(999)<1000
  //there should be a tighter bound, but 1000 is not large :P
  //and you can use an array for bounded cache
  let next = value.toString().split('').reduce((s, d) => s + d * d, 0)
  happy_cache.set(value, emotion_unknown)
  let result = isHappy(next)
  happy_cache.set(value, result)
  return result
}

//the SO console seems to have 50 line limit
//for (let i = 1; i < 100; ++i) {if (isHappy(i)) console.log(i);}
let happy_numbers=new Set;
for (let i = 1; i < 1000; ++i) {if (isHappy(i)) happy_numbers.add(i);}
console.log(...happy_numbers)

- apple apple

1

感谢您的输入并向我展示了我需要学习“Symbol”和“new Map”，我以前从未接触过这些术语。 - Hubbleduzz

很高兴能帮忙 :) 简单描述：Symbol 创建一个唯一的对象，而 Map 是将一个值映射到另一个值的容器。 - apple apple

0

function happy(n) {
  return n > 6
    ? happy([...`${n}`].reduce((sum,d) => sum+(d**2),0))
    : n === 1;
}

console.log(happy(1)); // true
console.log(happy(7)); // true
console.log(happy(19)); // true
console.log(happy(63)); // false
console.log(happy(133)); // true

如果 "n" 大于 "6"，则递归调用 "happy":

返回 n > 6 ? happy([...${n}].reduce((sum,d) => sum+(d**2),0))

在每次递归调用时，我们将更新 "n"

首先，我们将使用模板文字和拆分运算符将 "n" 转换为数组

[...`${n}`]

接下来，我们将使用“reduce”循环遍历新转换的数组。在每次迭代中，我们将对数组中的每个数字“d”进行平方运算，并将它们与“sum”连接起来。

[...`${n}`].reduce((sum,d) => sum+(d**2),0)

最后，我们将检查“n”或更新后的“n”是否等于“1”。

n === 1

- noirsociety

不幸的是，这是不正确的。你需要知道是否会循环，而不是是否达到一个不是 1 的个位数。这里有一个例子：7 -> 49 -> 130 -> 10 -> 1。 - Scott Sauyet

直到现在我才意识到。你说得对，逻辑不应该基于“n”是否是个位数。感谢指出这一点，Scott :) - noirsociety

虽然这是正确的，但你明白为什么它有效吗？这个解决方案感觉大多是巧合。它之所以有效，是因为每个数字都会命中1或循环[89→145→42→20→4→16→37→58→89]。结果发现，2、3、4、5和6属于后一类，但代码感觉好像是神奇地偶然发生的。 - Scott Sauyet

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nina Scholz · Accepted Answer

你可以先返回给定数字的检查结果（提前退出方法），并使用 Set 存储已经出现过的数字。

如果该数字为1，则很高兴返回true,
如果该数字之前已经出现过，则存在一个循环，返回false,
或者返回所有平方数位之和的递归调用结果。

function isHappy(value, seen = new Set) {
    if (value === 1) return true;
    if (seen.has(value)) return false;
    seen.add(value);
    return isHappy(value.toString().split('').reduce((s, d) => s + d * d, 0), seen);
}

console.log(isHappy(1));
console.log(isHappy(19));
console.log(isHappy(4));
console.log(isHappy(22));