Problem Link - Recurring Digit Sum in Recursion
Problem Statement:
Given a non-negative integer N, repeatedly sum its digits until the result has only one digit.
Approach:
We can solve this problem using recursion by repeatedly summing the digits of N and then checking if the sum has more than one digit. If so, we call the same function recursively with this sum until the result is a single-digit number.
- Base Case: If N is a single-digit number (i.e., N<10), return N.
- Recursive Case: If N has more than one digit, calculate the sum of its digits and recursively call the function with the new sum.
Complexity:
-
Time Complexity:
O(log N)since the number of digits inNreduces significantly with each recursion (from multiple digits to just one). -
Space Complexity:
O(log N)for the recursion stack because each recursion call processes the sum of digits of a progressively smaller number.