Problem Statement
The task is to calculate the sum of the digits of a non-negative integer using recursion.
Definition
- Given a non-negative integer, the sum of digits is the sum of all individual digits of that number.
- Example: For 123, the sum of digits is 1 + 2 + 3 = 6.
Example Inputs
Explanation: The sum of the digits of 123 is 1 + 2 + 3 = 6.
Approach - Use Recursion
Approach
Recursion is a method where a function calls itself. The idea here is to break the problem into smaller sub-problems by reducing the number at each recursive step. We can sum the digits by taking the last digit of the number (using modulus), adding it to the sum of the digits of the remaining number (by removing the last digit using division).
Steps
- If the number is 0, return 0 (base case: the sum of digits of 0 is 0).
- If the number is greater than 0:
- Take the last digit using modulus (
n % 10).
- Add it to the sum of the digits of the remaining number (
n // 10).
- Return the sum.
Time & Space Complexity
- Time Complexity: O(d), where
d is the number of digits in the given number. We make d recursive calls.
- Space Complexity: O(d), due to the recursion stack. Each recursive call adds a layer to the stack.
Code Snippet
Dry Run
Let’s dry run the code with the input n = 123:
- sumOfDigits(123): (123 % 10) + sumOfDigits(Math.floor(123 / 10)) = 3 + sumOfDigits(12)
- sumOfDigits(12): (12 % 10) + sumOfDigits(Math.floor(12 / 10)) = 2 + sumOfDigits(1)
- sumOfDigits(1): (1 % 10) + sumOfDigits(Math.floor(1 / 10)) = 1 + sumOfDigits(0)
- sumOfDigits(0): 0 (base case)
- Return from sumOfDigits(1): 1 + 0 = 1
- Return from sumOfDigits(12): 2 + 1 = 3
- Return from sumOfDigits(123): 3 + 3 = 6
Output:
Complexity Analysis
Time and Space Complexity
- Time Complexity: O(d), where
d is the number of digits in the number n. We need to process each digit once.
- Space Complexity: O(d) due to the recursion stack. The depth of the recursion is proportional to the number of digits in
n.
Conclusion
The recursive approach to summing the digits of a number is simple and intuitive. We break the problem down into smaller subproblems by removing the last digit in each recursive call. While this approach works well, the space complexity can grow with the size of the number, as each recursive call adds a new layer to the stack. An iterative solution might be more space-efficient in cases with large numbers.