Sum of Digits Using Recursion: flowchart, algorithm and program

This program reads an integer n and prints the sum of its digits using a recursive function sumOfDigits. The idea is that the digits of n are the last digit (n % 10) plus the digits of everything before it (n / 10).

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Read n.
  3. Step 3: Call sumOfDigits(n).
  4. Step 4: If n == 0, go to step 5; otherwise go to step 6.
  5. Step 5: Return 0. Go to step 7.
  6. Step 6: return (n % 10) + sumOfDigits(n / 10). Go to step 4.
  7. Step 7: Print sum of digits.
  8. Step 8: Stop.

Program in C, Python and Java

Sum of Digits Using Recursion program in C

#include <stdio.h>

int sumOfDigits(int n) {
    if (n == 0)
        return 0;
    return (n % 10) + sumOfDigits(n / 10);
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);
    printf("Sum of digits = %d\n", sumOfDigits(n));
    return 0;
}

Sum of Digits Using Recursion program in Python

def sum_of_digits(n):
    if n == 0:
        return 0
    return (n % 10) + sum_of_digits(n // 10)

n = int(input("Enter n: "))
print("Sum of digits =", sum_of_digits(n))

Sum of Digits Using Recursion program in Java

import java.util.Scanner;

public class Main {
    static int sumOfDigits(int n) {
        if (n == 0)
            return 0;
        return (n % 10) + sumOfDigits(n / 10);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n: ");
        int n = sc.nextInt();
        System.out.println("Sum of digits = " + sumOfDigits(n));
    }
}

Sample input: n = 1234
Output: Enter n: Sum of digits = 10

How it works

  • n % 10 gives the last digit of n, for example 1234 % 10 = 4.
  • n / 10 removes the last digit using integer division, so 1234 becomes 123, and the function calls itself with that smaller number.
  • The base case is n == 0: there are no digits left, so it returns 0 and the recursion stops.
  • On the way back, each call adds its own digit to the result of the inner call: 4 + (3 + (2 + (1 + 0))) = 10.
  • main() reads n with scanf, calls sumOfDigits(n) once, and prints the returned value.

Dry run (trace table)

StepLineBoxnOutput
19Start
212Read n1234
313Call sumOfDigits(n)1234
44n == 0?1234
56return (n % 10) + sumOfDigits(n / 10)1234
64n == 0?123
76return (n % 10) + sumOfDigits(n / 10)123
84n == 0?12
96return (n % 10) + sumOfDigits(n / 10)12
104n == 0?1
116return (n % 10) + sumOfDigits(n / 10)1
124n == 0?0
135return 00
146return (n % 10) + sumOfDigits(n / 10)1
156return (n % 10) + sumOfDigits(n / 10)12
166return (n % 10) + sumOfDigits(n / 10)123
176return (n % 10) + sumOfDigits(n / 10)1234
1813Print sum of digits1234Sum of digits = 10
1915Stop1234

Time and space complexity

Time: O(d) = O(log n) · Space: O(d) = O(log n). Each recursive call removes one digit, so there are d calls (d = number of digits) that stay on the call stack.

Common mistakes

  • Forgetting the base case n == 0, which makes the function call itself forever and crash with a stack overflow.
  • Using n % 10 on the recursive call instead of n / 10, so the number never gets smaller.
  • Not thinking about negative numbers: with a negative n in C, n % 10 gives a negative digit, so take the absolute value first if you need to support them.

Viva questions

Q1. What is the base case in sumOfDigits, and why is it needed?

The base case is `if (n == 0) return 0;` on line 4. It stops the recursion. Without it the function would keep calling itself forever and the program would crash with a stack overflow.

Q2. What do n % 10 and n / 10 do in this program?

n % 10 gives the last digit of n. n / 10 is integer division, so it drops that last digit and leaves the remaining number. For 123, n % 10 is 3 and n / 10 is 12.

Q3. Trace the function for n = 123. How does the answer 6 come out?

sumOfDigits(123) = 3 + sumOfDigits(12) = 3 + 2 + sumOfDigits(1) = 3 + 2 + 1 + sumOfDigits(0). sumOfDigits(0) returns 0, so the results add up on the way back to 6.

Q4. What does the program print if the input is 0?

It prints 0. The base case returns 0 straight away, which is also the correct digit sum of 0.

Q5. What happens if the user enters a negative number, for example -123?

In C, % keeps the sign of the dividend and / truncates toward zero. So -123 % 10 is -3 and the digits are added as negatives, giving -6. The program does not handle negatives properly. To fix it, take the absolute value first, for example `if (n < 0) n = -n;`.

Q6. What is the time and space complexity of this program?

The function is called once per digit, so the time is O(d), where d = number of digits, which is O(log n). The recursion goes d levels deep, so the stack space is also O(d).

Q7. Why is this called recursion, and how would you write it without recursion?

A function that calls itself on a smaller input is recursive. Here it calls itself on n / 10. The iterative version uses a while loop. Start with sum = 0, and while n > 0 do sum += n % 10; n /= 10;. It uses O(1) extra space.

Q8. What would change if you wanted the product of the digits instead of the sum?

Use `*` instead of `+`, and make the base case return 1 instead of 0. The result needs to start from 1, the identity for multiplication. Otherwise every product would become 0. You would also need to handle n = 0 separately, since its digit product should be 0.

Frequently asked questions

What is the base case in the recursive sum of digits?

The base case is n == 0, where the function returns 0. It means there are no digits left to add, so the recursion stops.

What does sumOfDigits return for n = 0?

It returns 0 straight away because the base case is hit on the first call, which is also the correct digit sum of 0.

What are the time and space complexity of this program?

Time is O(d) where d is the number of digits in n, since each call removes one digit. Space is also O(d) because of the recursion call stack.

More programs

← All programs

Try AI Flowchart free →