Count Every Decimal Digit with Recursion

Dividing by 10 removes exactly one digit, even when that digit is 0

Start with the positive integer 50720. Integer division by 10 removes its rightmost decimal position and keeps the remaining positions: 50720 becomes 5072, then 507, then 50, then 5. The first division removes a position containing 0, but that position still belongs to the number and must still be counted.

50720 / 10 = 5072
 5072 / 10 =  507
  507 / 10 =   50
   50 / 10 =    5

The value of the removed digit does not affect this process. A removed 0 occupies just as much of the decimal representation as a removed 5 or 7. After four divisions, only the one-digit value 5 remains, so the shrinking sequence has accounted for five digit positions in total.

The final one-digit value must contribute 1 to the answer

The recursive process should stop when n is less than 10, because every such positive n is one digit. For 50720, the last value is 5, so the base case must return 1. Every larger value removes one digit and adds 1 to the result returned for the smaller value.

int countDigits(int n) {
    if (n < 10) {
        return 1;
    }
    return 1 + countDigits(n / 10);
}

Applying the rule to 50720 gives return 1 + countDigits(5072). The same rule applies until the argument is 5. If the base case returned 0 instead, countDigits(5) would contribute nothing, so the four larger calls would return only 4. That would lose the final digit even though 5 is a valid digit.

The answer becomes visible while the recursive calls return

The calls first move down through the shrinking values, but the answer is assembled while those calls return. The call for 5 returns 1. That value lets the call for 50 return 2, then the call for 507 returns 3, the call for 5072 returns 4, and the original call for 50720 returns 5.

countDigits(5)     = 1
countDigits(50)    = 1 + 1 = 2
countDigits(507)   = 1 + 2 = 3
countDigits(5072)  = 1 + 3 = 4
countDigits(50720) = 1 + 4 = 5

This count depends on the number of recursive levels, not on whether a digit has a nonzero value. The two zeroes in 50720 still create positions in the sequence of calls: the final zero is removed by the first division, and the zero in 50 is removed by the next division. Neither zero needs to produce a nonzero value to be counted.

if (n < 10) return ___;

Removing one digit per call makes the cost logarithmic in the number

Each call performs constant work and changes n to integer n / 10, so the running time follows the recurrence T(n) = T(n / 10) + O(1) for positive n. For 50720, the five call arguments are 50720, 5072, 507, 50, and 5. The number of calls is the number of decimal digits, which is floor(log10(n)) + 1 for positive n.

Therefore the time complexity is O(log10 n). The calls remain on the call stack while the smaller calls finish, so the auxiliary stack space is also O(log10 n). For 50720, both costs are proportional to 5, even though the returned answer is only the final count.