Sum of Digits (Recursive)
Last Updated: June 7, 2026
Understanding the Problem
Two arithmetic facts split a number into a digit and a smaller number. The last digit is n % 10, the remainder after dividing by 10. The number with that last digit removed is n / 10, using integer division. For 1234, the last digit is 4 and the rest is 123.
So the digit sum of 1234 is 4 + (digit sum of 123). The part in parentheses is the same problem on a smaller number, which makes this recursive. Peeling continues, 123 gives 3 + (digit sum of 12), and so on until a single digit is left, where the sum is that digit.
Key Constraints:
ncan be0, and the digit sum of0is0. The base case must return0here rather than recursing.nis non-negative, son % 10is always a digit from0to9, andn / 10always moves toward0. The recursion is guaranteed to terminate.- The largest input has
10digits, so the recursion is shallow and the result fits easily in anint.
Approach 1: Recursion
Intuition
The digit sum of n is (n % 10) + sum(n / 10): the last digit plus the same problem on a shorter number, which the function computes by calling itself.
The recursion stops when one digit is left. When n is below 10, its digit sum is the number itself, so sum(n) = n. Integer division by 10 strictly shrinks any number of two or more digits, so every input eventually drops below 10 and reaches this base case. The base case also handles 0, since 0 is below 10 and returns 0.
Algorithm
- If
nis less than10, returnn. A single-digit number is its own digit sum. - Otherwise, return
(n % 10)plus the result of calling the function withn / 10.
Example Walkthrough
Input:
The first call is sum(1234). Its last digit is 4, so it returns 4 + sum(123). That call returns 3 + sum(12), which returns 2 + sum(1). Now 1 is below 10, so sum(1) returns 1 from the base case. The calls unwind: sum(12) returns 2 + 1 = 3, sum(123) returns 3 + 3 = 6, and sum(1234) returns 4 + 6 = 10. Each level contributed one digit, and the four digits 1, 2, 3, 4 added up to 10.
Code
- Time Complexity: O(d), where
dis the number of digits inn. Each call peels off one digit, so the number of calls equals the digit count, 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 fixed pair of operations: take the last digit with % 10, add it to a running total, then drop the digit with / 10. A loop can do the same and keep everything in one stack frame. Keep going until n reaches 0, adding each digit to the total along the way.
Algorithm
- Set an accumulator
totalto0. - While
nis greater than0, addn % 10tototal, then setnton / 10. - Return
total. When the input is0, the loop never runs andtotalstays0.
Example Walkthrough
Input:
The total starts at 0. With n = 1234, the loop adds 4 to make 4, then n becomes 123. It adds 3 to make 7, then n becomes 12. It adds 2 to make 9, then n becomes 1. It adds 1 to make 10, then n becomes 0 and the loop stops. The total is 10, the same answer the recursion produced from the same four digits.
Code
- Time Complexity: O(d), where
dis the number of digits inn. The loop runs once per digit, aboutlog10(n)steps. - Space Complexity: O(1). Only the accumulator is stored, and there is no recursion to grow the stack.