Sum of Digits - Implementation

Here's the recursive solution:

function sum_of_digits(n)
    if n < 10 then
        return n
    return (n mod 10) + sum_of_digits(n / 10)

Try tracing sum_of_digits(1234) yourself. What's the first call? When do you stop? You compute $4 + \text{sum}(123)$, which becomes $4 + 3 + \text{sum}(12)$, then $4 + 3 + 2 + \text{sum}(1)$, and finally $4 + 3 + 2 + 1 = 10$.

Time complexity: $O(\log n)$ since you process one digit per call.

Space complexity: $O(\log n)$ for the call stack.