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.

sorry, I forgot the add the test variable (num=19) and it's happy — Hubbleduzz
– Hubbleduzz, Commented Apr 4, 2020 at 8:16
you need to provide cycle detection i e. use a set with all numbers you've tried before — Turo
– Turo, Commented Apr 4, 2020 at 8:17

Nina Scholz · Accepted Answer · 2020-04-04 08:49:18Z

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

edited Apr 4, 2020 at 8:49

answered Apr 4, 2020 at 8:18

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

apple apple Over a year ago

the requirement is: replace the number by the sum of the squares of its digits

apple apple Over a year ago

I think it's correct answer now :) btw the downvote is not mine.

Hubbleduzz Over a year ago

All of these answers a lost on me, the concepts or notation used are too advanced atm('new Set', 'symbol', Map etc), but thanks for the assistance.

Hubbleduzz Over a year ago

Got it using @NinaScholz approach, first time using data structure which isn't just the standard initialized array or object. Feeling less defeatist now, many thanks.

Aadit M Shah · Accepted Answer · 2020-04-04 11:45:18Z

3

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.

answered Apr 4, 2020 at 11:45

Aadit M Shah

74.5k31 gold badges177 silver badges311 bronze badges

1 Comment

Hubbleduzz Over a year ago

thanks for the assistance, i will work on getting a grasp of floyds algorithm

apple apple · Accepted Answer · 2020-04-04 09:27:31Z

1

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)

edited Apr 4, 2020 at 9:27

answered Apr 4, 2020 at 9:09

apple apple

10.7k2 gold badges20 silver badges41 bronze badges

2 Comments

Hubbleduzz Over a year ago

thanks for the input and showing me that I need to learn 'Symbol' and 'new Map', i'd never come across those terms before

apple apple Over a year ago

glad to help :) short description: Symbol create a unique object, and Map is a container that map one value to another.

noirsociety · Accepted Answer · 2022-07-19 04:41:43Z

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

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

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

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)

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

n === 1

edited Jul 19, 2022 at 4:41

answered Jul 17, 2022 at 22:13

noirsociety

3741 gold badge3 silver badges13 bronze badges

3 Comments

Scott Sauyet Over a year ago

Unfortunately, this is not correct. You need to know if you ever cycle, not if you ever reach a single digit that's not 1. Here's an example: 7 -> 49 -> 130 -> 10 -> 1

noirsociety Over a year ago

I never realize that until now. You are absolutely right, in that, the logic shouldn't be based on whether "n" is a single digit. Thanks for pointing that out Scott :)

Scott Sauyet Over a year ago

While this is correct, do you understand why it works? This solution feels mostly coincidental. It happens to work because every number will either hit 1 or the loop [89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89]. It turns out that 2, 3, 4, 5, and 6 are in the latter category, but the code feels as though it happens upon this magically.

Collectives™ on Stack Overflow

Javascript, a simple recursive function

4 Answers 4

4 Comments

1 Comment

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

1 Comment

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related