Python Program to Find Sum of Digits Using Recursion

You can find the sum of digits of a number using recursion in Python by defining a function like def sum_of_digits(n): return n if n < 10 else n % 10 + sum_of_digits(n // 10) which adds the last digit to the sum of the remaining digits recursively.

Examples

Input123

Output6

Input0

Output0

Input9

Output9

How to Think About It

To find the sum of digits using recursion, think of the number as made of its last digit plus the rest. Use % to get the last digit and // to remove it. Keep adding the last digit to the sum of the remaining digits until the number is less than 10, which is the base case.

Algorithm

1

Get the input number.

2

Check if the number is less than 10; if yes, return the number itself.

3

Otherwise, find the last digit using modulus 10.

4

Call the function recursively with the number divided by 10 (integer division).

5

Add the last digit to the result of the recursive call and return the sum.

Code

python

def sum_of_digits(n):
    if n < 10:
        return n
    else:
        return n % 10 + sum_of_digits(n // 10)

number = 123
print("Sum of digits:", sum_of_digits(number))

Output

Sum of digits: 6

Dry Run

Let's trace the number 123 through the code

1

Initial call

sum_of_digits(123) checks if 123 < 10 (false), so it calculates 123 % 10 = 3 and calls sum_of_digits(12)

2

Second call

sum_of_digits(12) checks if 12 < 10 (false), calculates 12 % 10 = 2 and calls sum_of_digits(1)

3

Base case

sum_of_digits(1) checks if 1 < 10 (true), returns 1

4

Return from second call

sum_of_digits(12) returns 2 + 1 = 3

5

Return from initial call

sum_of_digits(123) returns 3 + 3 = 6

Call	Number	Last Digit	Recursive Call	Return Value
1	123	3	sum_of_digits(12)	6
2	12	2	sum_of_digits(1)	3
3	1	1	base case	1

Why This Works

Step 1: Base case

When the number is less than 10, it means it has only one digit, so we return it directly using return n.

Step 2: Recursive step

We separate the last digit using n % 10 and add it to the sum of digits of the remaining number found by n // 10.

Step 3: Recursive call

The function calls itself with the smaller number until it reaches the base case, accumulating the sum of digits on the way back.

Alternative Approaches

Using string conversion and recursion

python

def sum_of_digits_str(n):
    s = str(n)
    if len(s) == 1:
        return int(s)
    else:
        return int(s[-1]) + sum_of_digits_str(int(s[:-1]))

print("Sum of digits:", sum_of_digits_str(123))

This method converts the number to a string and processes digits as characters, which is easy to understand but less efficient than pure arithmetic.

Using a loop (non-recursive)

python

def sum_of_digits_loop(n):
    total = 0
    while n > 0:
        total += n % 10
        n //= 10
    return total

print("Sum of digits:", sum_of_digits_loop(123))

This iterative approach avoids recursion and is efficient for large numbers but does not use recursion as requested.

Complexity: O(d) time, O(d) space

Time Complexity

The function processes each digit once, so the time grows linearly with the number of digits d.

Space Complexity

Each recursive call adds a layer to the call stack, so space used is proportional to the number of digits d.

Which Approach is Fastest?

The arithmetic recursion and loop methods are faster and use less memory than string conversion, which involves extra overhead.

Approach	Time	Space	Best For
Arithmetic Recursion	O(d)	O(d)	Learning recursion with math operations
String Conversion Recursion	O(d)	O(d)	Easier to understand but less efficient
Iterative Loop	O(d)	O(1)	Best for performance and large inputs