Count Digits (Recursive)
Last Updated: June 7, 2026
Understanding the Problem
Dividing a whole number by 10 and discarding the remainder removes its last digit. The number 1234 divided by 10 is 123, which has one fewer digit. Repeat and 123 becomes 12, then 1, which shrinks no further.
The digit count of 1234 is one more than the digit count of 123. That phrasing is recursive, since 123 is the same problem on a smaller number. The division continues until a single-digit number is left, which is where the counting bottoms out.
Key Constraints:
ncan be0, which is written with a single digit, so the answer for0is1. The base case has to treat0as one digit rather than zero digits.nis non-negative, so integer division by10always moves toward0and the recursion is guaranteed to terminate.- The largest input has
10digits, so the recursion depth stays small and the result fits comfortably in anint.
Approach 1: Recursion
Intuition
The recursive step is count(n) = 1 + count(n / 10): one digit removed, plus the count of what remains.
The base case stops the recursion. Once n is below 10, it is a single-digit number, so count(n) = 1 for any n from 0 to 9. Integer division by 10 strictly shrinks any number with two or more digits, so every input eventually falls below 10 and hits the base case. This also handles 0 correctly, since 0 is below 10 and counts as one digit.
Algorithm
- If
nis less than10, return1. A single-digit number, including0, has one digit. - Otherwise, return
1plus the result of calling the function withn / 10.
Example Walkthrough
Input:
The first call is count(12345). Since 12345 is not below 10, it returns 1 + count(1234). That call returns 1 + count(123), which returns 1 + count(12), which returns 1 + count(1). Now 1 is below 10, so count(1) returns 1 from the base case. The calls unwind: count(12) returns 1 + 1 = 2, count(123) returns 1 + 2 = 3, count(1234) returns 1 + 3 = 4, and count(12345) returns 1 + 4 = 5. Five chops were needed to reach a single digit, so the answer is 5.
Code
- Time Complexity: O(d), where
dis the number of digits inn. Each call removes one digit, so the number of calls equals the digit count, which is aboutlog10(n). - Space Complexity: O(d). One stack frame is held per digit until the base case returns and the calls unwind.
Approach 2: Iterative Division
Intuition
The recursion repeats a single action: divide by 10 and add one to a counter. A loop can do the same thing without the call stack. Keep dividing n by 10 until it reaches 0, and count how many divisions that takes. Starting the counter at 1 and dividing while n is at least 10 keeps the handling of 0 clean, since 0 already counts as one digit before the loop runs.
Algorithm
- Set a counter
countto1, since every number has at least one digit. - While
nis at least10, dividenby10and add1tocount. - Return
count.
Example Walkthrough
Input:
The counter starts at 1. With n = 12345, the loop divides to 1234 and the counter becomes 2. Then 1234 becomes 123 and the counter becomes 3, 123 becomes 12 and the counter becomes 4, and 12 becomes 1 and the counter becomes 5. Now n is 1, which is below 10, so the loop stops and returns 5. This matches the recursive answer, since both versions divide by 10 the same number of times.
Code
- Time Complexity: O(d), where
dis the number of digits inn. The loop runs once per digit, which is aboutlog10(n)steps. - Space Complexity: O(1). Only the counter is stored, and there is no recursion to grow the stack.