Algorithm

Sum of Digits

Recursion Pattern

Sum of Digits

Given a non-negative integer n, return the sum of its decimal digits. For example the digits of 1234 sum to 1 + 2 + 3 + 4 = 10. Return the single integer sum. Solve it recursively, peeling one digit at a time.

CONSTRAINTS
  • 0 <= n <= 10⁹
  • n is an integer
  • A single-digit n (0–9) is its own digit sum
EXAMPLE 1
Input: n = 0
Output: 0
0 is a single digit, so it is its own digit sum. Base case.
EXAMPLE 2
Input: n = 7
Output: 7
A single-digit number returns immediately without recursing.
EXAMPLE 3
Input: n = 1234
Output: 10
1 + 2 + 3 + 4 = 10.
EXAMPLE 4
Input: n = 408
Output: 12
4 + 0 + 8 = 12. The middle zero contributes nothing but is still peeled off like any other digit.
Should I convert the number to a string and add the characters?
You can, but arithmetic (% 10 and // 10) avoids the conversion and is the point of the exercise — it exposes the 'peel one, recurse on the rest' structure directly.
What is the base case exactly?
When n < 10 the number is a single digit and equals its own digit sum, so return n. Reaching it is guaranteed because // 10 strictly shrinks n every call.
Does this recurse deeply enough to overflow the stack?
No. The depth equals the number of digits — at most 10 for n up to 10⁹ — so the stack stays tiny. Digit-based recursion is inherently shallow.
What about negative numbers?
The constraints keep n non-negative. A negative n would make % and // behave in language-specific ways and would need its sign stripped first.

We want the sum of a number's digits: 1234 → 1 + 2 + 3 + 4 = 10. This looks like it needs a loop over characters, but there is a cleaner recursive view that reuses exactly the skeleton from Factorial — one call per step, combine on the way back up. That single-call shape has a name: linear recursion.

Finding the smaller copy

The two tools for taking a number apart digit by digit are arithmetic, not string conversion:

- n % 10 gives the last digit (1234 % 10 = 4).
- n // 10 (integer division) removes the last digit (1234 // 10 = 123).

So the sum of the digits of 1234 is 4 plus the sum of the digits of 123. In general, digitSum(n) = (n % 10) + digitSum(n // 10). The answer for n is built from the answer for a strictly smaller number (one digit shorter) — the recursive signal again.

Filling the three slots

Recall the skeleton from Factorial: base case, progress, combine. Fill it in:

- Base case: when n is a single digit (n < 10), the digit sum is just n itself — return it, no recursion.
- Progress: n // 10 chops off a digit, so each call is strictly smaller and marches toward the single-digit base.
- Combine: add the peeled digit n % 10 to whatever the smaller call returns.
python
def sum_digits(n):
    if n < 10:                     # base case: one digit left
        return n
    return (n % 10) + sum_digits(n // 10)
Crucial Notethe base case must be n < 10, not n == 0. Both eventually terminate, but n < 10 stops one step earlier and, more importantly, it directly states the real base fact — a single digit is its own sum. Using n == 0 also works (a lone digit d becomes d + sum_digits(0) = d + 0) but it relies on the quieter fact that the digits of 0 sum to 0; either is fine as long as it is a true stopping fact the recursion is guaranteed to reach.
Worked Example:sum_digits(408)
- sum_digits(408): 408 ≥ 10. Peel 408 % 10 = 8, recurse on 408 // 10 = 40. Frame waits, owing "+ 8".
- sum_digits(40): 40 ≥ 10. Peel 0, recurse on 4. Frame waits, owing "+ 0".
- sum_digits(4): 4 < 10 — base case. Return 4.
- Unwind: 4 → 0 + 4 = 4 → 8 + 4 = 12. Answer: 12 (and indeed 4 + 0 + 8 = 12).

Notice this is linear recursion: each call makes exactly one recursive call, so the call stack goes straight down to a depth equal to the number of digits and then straight back up — no branching. That keeps it to O(d) time and O(d) stack space, where d is the digit count (at most 10 for values up to 10⁹).

The takeaway

Linear recursion is the simplest recursive shape and the one to master first: a single chain of calls, work combined on the return trip, cost proportional to the depth. Any "process one element, then handle the rest" problem — summing a list, reversing a string, walking a linked list — fits this mold. The moment a function needs to make two calls instead of one, the straight chain becomes a tree, the cost can explode, and we are in the world of the next problem, Fibonacci.

O(d) Iterative Loop
→
O(d) Time · O(d) Stack Linear Recursion