Javascript, a simple recursive function

Question

I need help implementing a recursive function. This is my first time attempting recursion outside of the standard 'factorial' that us newbs first learn.

I am able to get the correct answer in the console, but I can't figure out how to make my function recognize that it has produced the correct answer.

The challenge: "Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers."

My attempt:

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)

I've use while loops and made different attemps at performing the base case test, but no luck. Any help would be greatly appreciated.

Answer 1

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

1. if "n" is greater than "6" then invoke "happy" recursively:

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

2. on each recursively invocation, we'll update "n"

• first, we'll convert "n" into an array with template literal & split operator

[...`${n}`]

• next, we'll loop over the newly converted array with "reduce". on each iteration, we'll square up each digit "d" from the array the concatenate them with "sum"

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

3. lastly, we'll check whether "n" or the updated "n" is equal to "1

n === 1

Answer 2

Here's a way to compute the answer without using a list of previously seen numbers.

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

Unlike Nina's answer, this solution is memory efficient.

Answer 3

Here is a globally-cached version of @Nina 's answer

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)

Answer 4

You could return a check of the given number first (exit early approach) and use a Set for seen numbers

• if one, is happy return true,
• is the number is seen before, then you got a cycle, then return false,
• or return the result of the recursive call with the sum of all squared digits.

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