How to implement recursive algorithm correctly?

Question

I'm trying to solve the algorithm on codewars website. As a beginner i experience difficulty to implement various programming technique and lack basic programming concepts such as scoping, hoisting and so on. Anyway i'm determined to solve the problem.

The instructions says:

Write a function, persistence, that takes in a positive parameter num and returns its multiplicative persistence, which is the number of times you must multiply the digits in num until you reach a single digit.

persistence(39) === 3 // because 3*9 = 27, 2*7 = 14, 1*4=4
                           // and 4 has only one digit
persistence(999) === 4 // because 9*9*9 = 729, 7*2*9 = 126,
                            // 1*2*6 = 12, and finally 1*2 = 2
persistence(4) === 0 // because 4 is already a one-digit number

For now i just want to achive this result 3*9 = 27, 2*7 = 14, 1*4=4 However i got stuck. I know i miss something, please give me some valuable suggestion!

My code looks like this:

function persistence(num) {
    var total = 1;
    var step = 0;
    var number = multiple(num);
    while (step < 3) {
        for (var i = 0; i < number.length; i++) {
            total *= splitNumbers[i];
        }
        multiple(number);
        step += 1;
    }
}

function multiple(num) {
    var splitNumbers = num.toString().split('');
    var a = splitNumbers[0];
    var b = splitNumbers[1];
    return a * b;
}
persistence(39);

number is a number. Numbers don't have a length property so i < number.length will set the value of i to undefined. BTW, this isn't recursion. ;-) — RobG
– RobG, Commented Feb 26, 2017 at 8:53

trincot · Accepted Answer · 2017-02-26 08:59:03Z

It is strange that in the second function you calculate a product (ignoring all digits except the first two), and then in a the main function you treat it as a string (which it isn't), and start multiplying those digits again. This is not the principle of recursion: you should do some action just once, and then do the recursive call.

Here is a solution:

function persistence(num) {
    var digits = getDigits(num);
    if (digits.length === 1) return 0; // number has only 1 digit, so we're done
    var product = getProduct(digits);
    return 1 + persistence(product); // we performed one transformation, now recurse
}

function getDigits(num) {
    return num.toString().split('').map(Number); // convert chars to numbers
}

function getProduct(nums) {
    return nums.reduce(function (a, b) { // nice way to get 1 result from array
        return a * b;
    }, 1);
}

console.log(persistence(39));

rgthree · Accepted Answer · 2017-02-26 09:24:56Z

1

Start with a single function that returns the result if your condition is met (there is only one digit left). If there is not, then return the result of the next iteration, passing in the state (the current count) that you want to keep track of. Perhaps something like this:

function persistence(num, opt_count) {
  num = parseInt(num, 10); // Assume we're dealing with only ints.
  var count = opt_count || 0; // Count is optional, so make sure we init.

  if (num > 9) {
    var digits = String(num).split(''); // Split our number as string.
    num = digits.shift();
    do {
      num *= digits.shift(); // Note, multiplication will cast back automatically.
    } while(digits.length);
    count++; // Increment our count
  }

  if (num < 10) return count; // Return our count if we're under 10.
  return persistence(num, count); // Recurse with our current state.
}

console.log('39:  ' + persistence(39));     // 3
console.log('999: ' + persistence(999));    // 4
console.log('4:   ' + persistence(4));      // 0

edited Feb 26, 2017 at 9:24

answered Feb 26, 2017 at 9:03

rgthree

7,28319 silver badges21 bronze badges

1 Comment

NZMAI Over a year ago

do { num *= digits.shift(); } while(digits.length); count++; } Great implementation! I should take it into account! Is it some kind of pattern of programming that may be used it other situations?

RobG · Accepted Answer · 2017-02-26 09:34:17Z

There are a couple of issues in your code:

function persistence(num) {
    var total = 1;
    var step = 0;
    // This will return a number
    var number = multiple(num);

    while (step < 3) {
        // Here number is a number, which doesn't have a length property so
        // the loop never runs. However, once you fix that...
        for (var i = 0; i < number.length; i++) {

            // splitNumbers is in the multiple function, you can't access it
            // from this function
            total *= splitNumbers[i];
        }
        multiple(number);
        step += 1;
    }
    // The function doesn't have a return statement, so even if it works,
    // it returns undefined
}

function multiple(num) {
    var splitNumbers = num.toString().split('');
    var a = splitNumbers[0];
    var b = splitNumbers[1];
    return a * b;
}

console.log(persistence(39));

So fixing your code:

function persistence(num) {
  var total = 1;
  var step = 0;
  var number = multiple(num);
  // Make splitNumbers available locally
  var splitNumbers = String(number).split('');

  while (step < 3) {
    // Use the length of splitNumbers, not number
    for (var i = 0; i < splitNumbers.length; i++) {
      total *= splitNumbers[i];
    }
    multiple(number);
    step += 1;
  }
  // Return the accumulated step count
  return step;
}

function multiple(num) {
  var splitNumbers = num.toString().split('');
  var a = splitNumbers[0];
  var b = splitNumbers[1];
  return a * b;
}

console.log(persistence(39));

But that isn't using recursion, you're using sequential programming, which runs faster than recursion (though not necessarily noticeably) but is usually more code.

Other answers show some good alternative solutions, here's one using recent features (and recursion):

function persistence(num, steps = 0) {
  if (num > 9) steps++;
  var total = (num || 0).toString().split('').reduce((a, b) => a * b);
  return total > 9? steps += persistence(total) : steps;
}

[39, 999, 4].forEach(function(num) {
  console.log(num + ' : ' + persistence(num));
});

Ohhh you have provided solution. I tried to avoid looking at workable code as much as possible. But that is OK! Never mind)))

Collectives™ on Stack Overflow

How to implement recursive algorithm correctly?

3 Answers 3

Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related