CODEWITHSUNDEEP
javarecursionintegerdigits
Griezy
Griezy

Reputation: 55

Using recursion to determine the number of digits

I'm currently stuck on one line of code that I'm not fully understanding. So, I'm reading example codes from the book, and one of "programs" used recursion to determine the number of digits in an integer n. The one line of code that I got stuck at and do not fully understand is:

if (number >= 10) {
    return numberOfDigits(number / 10) + 1;

For an example, this makes the number 42 return 2, which it's supposed to do. But how exactly does the function return 2? 42 divided by 10 is equal to 4,2 or 4. That plus 1 is 5, so how does it return 2?

Upvotes: 0

Views: 3077

Answers (2)

Tim Biegeleisen
Tim Biegeleisen

Reputation: 521073

The full method probably looks something like this:

public int numberOfDigits(int number) {
    if (number >= 10) {
        return numberOfDigits(number / 10) + 1;
    }

    // base case: only one digit
    return 1;
}

By inspection, if we pass a two digit number, the if statement will be hit, which will return whatever the recursive call of the input / 10 is, plus one. Let's say the input were 42. In this case, it would return numberOfDigits(42 / 10) + 1. We know that numberOfDigits(4) returns 1, so this would return a total of 2, which is correct.

Using inductive reasoning, we can build up to convince ourselves of any number of arbitrary length.

Side note: In my travels, I have more often seen the base case handled first using an if statement, with the inductive case happening by default. So, I would have expected to see this code:

public int numberOfDigits(int number) {
    if (number < 10) return 1;

    return numberOfDigits(number / 10) + 1;
}

Upvotes: 0

rgettman
rgettman

Reputation: 178263

Recursion is a way to get one call of the method to perform some of the work, while deferring the remainder of the work to making another recursive call. Here, a "number of digits" recursive method says that the number of digits in a number is equal to 1 for the last digit plus the number of digits remaining after the last digit is removed.

In the return statement, the + 1 counts the last digit in the number, while number / 10 performs truncating integer division to remove the last digit. The recursive call counts the digits in the number with the last digit removed.

What you haven't shown is the base case of the recursion, when the number is single-digit (not greater than or equal to 10). That is simply 1 digit. The value 4 is not figured into the calculation. The method effectively counts the digits, one at a time, until there are no more digits left. There is one recursive method call per digit.

Upvotes: 2

Related Questions