Sum of Digits Using Recursion in Python

Computing the sum of digits of a number is a classic introductory algorithm. While straightforward to implement iteratively using a while loop, solving it recursively provides an intuitive foundation for understanding recurrence relations, call stack behavior, and structural decomposition.

Unlike an array or list where elements can be accessed directly using an index (e.g., arr[i]), an integer does not support index-based lookups without converting it to a string. Instead, arithmetic operations can extract individual digits and reduce the problem size.

---

1. Problem Decomposition & Arithmetic Operators

To recursively sum the digits of an integer $N$, we break down the number into two parts on each step:

1. The Unit’s Digit (Rightmost digit): Extracted via the modulo operator (%).
2. The Remaining Prefix: Extracted via floor division (//).

The Math Operations

For any non-negative base-10 number:

$\text{unit\_digit} = N \pmod{10}$ $\text{remaining\_number} = \lfloor N / 10 \rfloor$

Example with 123:

• 123 % 10 = 3 (Extracts the unit digit)
• 123 // 10 = 12 (Removes the unit digit, leaving the prefix)

Repeating this operation peels off digits from right to left until all digits have been processed.

---

2. Recurrence Relation & Base Case

A recursive solution requires two critical components: the recursive step (recurrence relation) and a termination condition (base case).

The Recurrence Relation

The sum of digits of a number $N$ can be defined as the sum of its unit digit plus the sum of digits of the remaining number:

$\text{SOD}(N) = (N \pmod{10}) + \text{SOD}(N \mathbin{/\!} 10)$

The Base Case

When repeatedly dividing an integer by 10, the process eventually reaches the most significant digit (e.g., 1 // 10 = 0).

When the remaining number drops to 0, there are no further digits to process:

$\text{SOD}(0) = 0$

If the base case is omitted or incorrect, the recursion will not terminate, resulting in a RecursionError: maximum recursion depth exceeded in Python.

---

3. Visualizing the Call Stack

Consider computing sod(123):

graph TD
    A["sod(123)"] -->|"3 + sod(12)"| B["sod(12)"]
    B -->|"2 + sod(1)"| C["sod(1)"]
    C -->|"1 + sod(0)"| D["sod(0)"]
    D -->|"returns 0"| C
    C -->|"returns 1 + 0 = 1"| B
    B -->|"returns 2 + 1 = 3"| A
    A -->|"returns 3 + 3 = 6"| OUT["Final Output: 6"]

Call Stack Unwinding Phase

1. Pushing Frames:

   • sod(123) calls 3 + sod(12)
   • sod(12) calls 2 + sod(1)
   • sod(1) calls 1 + sod(0)
   • sod(0) hits the base condition and returns 0

2. Popping Frames:

   • sod(1) returns 1 + 0 = 1
   • sod(12) returns 2 + 1 = 3
   • sod(123) returns 3 + 3 = 6

---

4. Python Implementation

Below is the clean, typed implementation matching the recursive formulation:

def sod(number: int) -> int:
    """
    Computes the sum of digits of a non-negative integer using recursion.
    """
    # Base Case: When the remaining number reaches 0, no digits are left
    if number == 0:
        return 0
    
    units_digit = number % 10
    remaining_number = number // 10
    
    # Recurrence Relation
    return units_digit + sod(remaining_number)

def sum_digits(number: int) -> int:
    """
    Wrapper function to handle inputs and edge cases.
    """
    # Handle negative numbers if necessary
    number = abs(number)
    
    if number == 0:
        return 0
        
    return sod(number)

# Verification
if __name__ == "__main__":
    print(f"Sum of digits for 123: {sum_digits(123)}")      # Output: 6
    print(f"Sum of digits for 12321: {sum_digits(12321)}")  # Output: 9

---

5. Complexity Analysis

Let $N$ be the input number and $d$ be the number of digits in $N$, where $d = \lfloor \log_{10}(N) \rfloor + 1$.

Metric	Complexity	Explanation
Time Complexity	$\mathcal{O}(\log_{10} N)$	In each recursive step, $N$ is divided by 10. The number of calls equals the number of digits $d$.
Space Complexity	$\mathcal{O}(\log_{10} N)$	Each recursive call consumes memory on the execution call stack. There are $d + 1$ active stack frames at peak depth.

---

6. Recursive vs. Iterative Comparison

Consideration	Recursive Approach	Iterative Approach (while n > 0)
Auxiliary Space	$\mathcal{O}(d)$ due to call stack frames	$\mathcal{O}(1)$ auxiliary space
Stack Safety	Can raise RecursionError if $d > 1000$ in Python	No stack limit issues
Pedagogical Value	High: builds intuition for divide-and-conquer and state reduction	Low: standard loop accumulation
Performance	Function call overhead per digit	Minimal overhead per iteration

---

Key Takeaways

• When working with integers recursively, integer division (// 10) shrinks the input state, while modulo arithmetic (% 10) extracts the target unit.
• The base case corresponds to the point where the number reaches 0 after removing the most significant digit.
• Mastering this “one-dimensional” recursion forms the building block for multi-dimensional recursive strategies, backtracking, and tree traversals.