Sum of Digit of a Number Using Recursion

Problem Statement

Given a number, we need to find sum of its digits using recursion.

Examples

Example 1:

Input: number = 12345
Output: 15

Explanation: 1+2+3+4+5 = 15

Theory

To calculate the sum of digits of a number using recursion, we can follow these steps:

1. Base Case: If the number is less than 10, return the number itself.
2. Recursive Step: Extract the last digit of the number and add it to the sum of digits of the rest of the number.
3. Addition: Return the sum obtained from the recursive call.

Different Approaches

1️⃣ Recursion

Let the number be 12345. 

• Step 1-> 12345 % 10 which is equal-too 5 + ( send 12345/10 to next step ) 
• Step 2-> 1234 % 10 which is equal-too 4 + ( send 1234/10 to next step ) 
• Step 3-> 123 % 10 which is equal-too 3 + ( send 123/10 to next step ) 
• Step 4-> 12 % 10 which is equal-too 2 + ( send 12/10 to next step ) 
• Step 5-> 1 % 10 which is equal-too 1 + ( send 1/10 to next step ) 
• Step 6-> 0 algorithm stops 

Code Implementation in C++:

#include <iostream>
using namespace std;

// Function to calculate sum of digits of a number using recursion
int sumOfDigits(int n) {
    // Base case: if the number is less than 10, return the number itself
    if (n < 10)
        return n;
    
    // Recursive step: extract the last digit and add it to the sum of digits of the rest of the number
    return n % 10 + sumOfDigits(n / 10);
}

int main() {
    int num = 12345;

    cout << "Sum of digits of the number " << num << " is " << sumOfDigits(num) << endl;

    return 0;
}

Output:

Sum of digits of the number 12345 is 15

Complexity Analysis:

• Time Complexity:O(log n)
  • Since the number of recursive calls is proportional to the number of digits in the number.
• Space Complexity:O(log n)
  • Due to the recursive stack, which can go as deep as the number of digits in the number.