CODEWITHSUNDEEP
javascriptrecursion
burtonLowel
burtonLowel

Reputation: 794

Javascript: How to recursively return a counter?

In the example below, I don't want to make a counter as a param. Rather, I just want to return '+ 1' each time so that what gets returned is the number of steps it takes. My issue lies with the base case. If I do return + 1, I get the correct number of steps plus one additional step so I tried just return but that delivers NaN. Is it even possible?

var numberOfSteps  = function(num) {

    if (num == 0) {
        return;
    } else {
        if (num % 2 == 0) {
            return 1 + numberOfSteps(num/2);
        } else {
            return 1 + numberOfSteps(num - 1);
        }
    }
};

edit : The goal is to track how many steps it takes to reduce a number to 0. If it's even, divide by 2 or else subtract by 1. Ultimately, I want to return the number of steps it takes for any given number to get reduced to 0 following those rules

Upvotes: 0

Views: 194

Answers (2)

Scott Sauyet
Scott Sauyet

Reputation: 50807

I hope the point has gotten through in the long comment thread and other answers that return + 1 is equivalent to return (+1), that is, return the integer positive one. And since there are no steps to take once you've reached zero, +1 is the wrong answer. Similarly, a plain return is functionally equivalent to return undefined. But undefined is not a number, and you're going to run into problems if you later try to add 1 to it. So the solution from the comments or other answers to return the correct number of steps, which in this case 0, will fix your code.

I would like to point out another way to solve this, though:

const numberOfSteps = (n) =>
  n <= 0
    ? 0
    : 1 + numberOfSteps (n % 2 == 0 ? n / 2 : n - 1)

console .log (numberOfSteps (12))

There are superficial differences here from the other solutions, such as using an arrow function, using a conditional statement (ternary) rather than if-statements, and using <= 0 instead of < 0 to avoid possible infinite loops on negative numbers.

But the fundamental difference is that this code only has one recursive branch. I think this is a better match to the problem.

We can think of this as a function which answers "How many steps does it take to reach 0 from our input number if each step cuts even numbers in half and subtracts one from odd ones?" Well that logically leads to a base case (we're already at 0) so have to return 0, and a recursive one (we're at some positive integer) so have to add 1 to the total steps required from our next entry.

By doing this single recursive call and adding one to the result, we make it clearer what the recursion is doing.

If this is unclear, then this alternative might show what I mean:

const takeStep = (n) =>
  n % 2 == 0 ? n / 2 : n - 1

const numberOfSteps = (n) =>
  n <= 0
    ? 0
    : 1 + numberOfSteps (takeStep (n))

Upvotes: 3

Codebling
Codebling

Reputation: 11382

Think you just need to return 0 when it's...zero. 

var numberOfSteps  = function(num) {

    if (num == 0) {
        return 0;
    } else {
        if (num % 2 == 0) {
            return 1 + numberOfSteps(num/2);
        } else {
            return 1 + numberOfSteps(num - 1);
        }
    }
}

return + 1 maybe doesn't do what you think it does: it returns the number 1. + here means positive not negative, there is no addition or subtraction going on. It will also give you one too many steps.

return; by itself returns undefined, which when converted to a Number, translates to NaN, because, well, it's not a number.

Upvotes: 2

Related Questions