Sum of Digits Using Recursion
Description
Given a non-negative integer n, return the sum of its decimal digits, using recursion.
Examples
Example 1
Input: n = 1234
Output: 10
Explanation: 1 + 2 + 3 + 4 = 10.
Example 2
Input: n = 7
Output: 7
Explanation: A single digit is its own sum.
Example 3
Input: n = 0
Output: 0
Explanation: 0 has digit sum 0.
Example 4
Input: n = 1000
Output: 1
Explanation: 1 + 0 + 0 + 0 = 1: zeros add nothing.
Constraints
- 0 ≤ n ≤ 10^9
Editorial
Approach - The Last Digit Plus the Rest
Intuition
n % 10 is the last digit and n // 10 is everything before it: 1234 is 123 and 4. So the digit sum of n is its last digit plus the digit sum of n // 10, the same problem with one digit fewer. When no digits are left, n is 0, and the sum is 0.
In JavaScript, / gives a fraction, so the rest is Math.floor(n / 10); in Java and C++, / on two ints already drops the remainder.
Step-by-Step Explanation
Let's trace Example 1, n = 1234:
digits(1234) = 1234 % 10 + digits(123) = 4 + 6 = 10.digits(123) = 123 % 10 + digits(12) = 3 + 3 = 6.digits(12) = 12 % 10 + digits(1) = 2 + 1 = 3.digits(1) = 1 % 10 + digits(0) = 1 + 0 = 1.digits(0)is the base case: it returns 0.
The Last Digit Plus the Rest — Each call peels off the last digit and waits for the rest's sum.
Algorithm
- If
nis 0, return 0. - Otherwise return
n % 10 + digits(n // 10).
Code
class Solution {
public:
int sumOfDigits(int n) {
if (n == 0) return 0;
return n % 10 + sumOfDigits(n / 10);
}
};
class Solution:
def sumOfDigits(self, n: int) -> int:
if n == 0:
return 0
return n % 10 + self.sumOfDigits(n // 10)
class Solution {
public int sumOfDigits(int n) {
if (n == 0) return 0;
return n % 10 + sumOfDigits(n / 10);
}
}
var sumOfDigits = function(n) {
if (n === 0) return 0;
return n % 10 + sumOfDigits(Math.floor(n / 10));
};
Complexity Analysis
Time Complexity: O(log n)
One call per digit: at most 10 digits, 11 calls with the base case.
Space Complexity: O(log n)
One frame per digit waits on the stack.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Returning 0 at the last digit. if n < 10:
On n = 1234 it returns 9; the answer is 10. When one digit is left, that digit still counts. Returning 0 there drops the leading digit of every number: stop at 0 instead, or return n itself when it's below 10.
Dividing with /. self.sumOfDigits(n / 10)
On n = 1234 it returns 11.111111111111118; the answer is 10. In Python, n / 10 is a float: 1234 / 10 is 123.4, never a whole number again, and the remainders pick up fractions. The recursion needs //, which drops the last digit.
Adding the rest instead of its digits. return n % 10 + n // 10
On n = 1234 it returns 127; the answer is 10. n // 10 is the rest of the number, not the sum of its digits: for 1234 that's 123, not 6. The recursion has to add up the rest's digits too.
Where This Pattern Is Taught
This problem practises a value returned through every frame, one digit per call. It's taught in Introduction to Recursion.