ISC Practicals and Theory - Sum of Digits (Recursive)

The sum of the digits of a number is found by adding its digits one by one. Using recursion, the method sumDigits() takes off the last digit with % 10, then calls itself on the remaining digits (/ 10) until no digits are left.

Definition

The sum of digits of a number is the total of all its digits. For example:

• $2947$: $2 + 9 + 4 + 7 = 22$
• $90507$: $9 + 0 + 5 + 0 + 7 = 21$

The last digit of a number is num % 10 and the number without its last digit is num / 10 (integer division). So the sum of digits of $2947$ is $7$ plus the sum of digits of $294$.

Recursion is a method calling itself. It needs a base case (stops without calling itself) and a recursive case (calls itself with a smaller problem).

Rules used in this program

• A negative number is rejected with an error message; only 0 or a positive number is accepted.
• For 0 the answer is 0, since the base case returns 0 straight away. Single-digit numbers return the digit itself.
• The number is an int, so values up to 2147483647 can be entered; any such number has at most 10 digits, so the sum cannot overflow.

Algorithm

1. Start. In main(), create an object ob of the class SumDigits.
2. Call accept() to read the number n.
3. If n is negative, print an error message and stop.
4. Otherwise call sumDigits(n) and store the value in total. Inside sumDigits(num):
   • Base case: if num == 0, return 0 (no digits left).
   • Recursive case: otherwise return num % 10 + sumDigits(num / 10): the last digit plus the sum of the remaining digits. Each call removes one digit, so num finally becomes 0.
5. Call display() to print the sum.
6. Stop.

Program

The method accept() reads the number, sumDigits() is the recursive method and display() prints the sum.

import java.util.*;
/** Class SumDigits: finds the sum of the digits of a number using recursion. */
class SumDigits
{
    int n;      // the number entered (0 or more)
    int total;  // sum of the digits of n

    /** Reads the number from the user. */
    void accept()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number (0 or more): ");
        n = sc.nextInt();
    }

    /**
     * Recursive method: returns the sum of the digits of num.
     * num: the number whose digits are added (num >= 0)
     */
    int sumDigits(int num)
    {
        if (num == 0)                         // base case: no digits left
            return 0;
        return num % 10 + sumDigits(num / 10); // recursive case: last digit + sum of the remaining digits
    }

    /** Shows the sum. */
    void display()
    {
        System.out.println("Sum of the digits of " + n + " = " + total);
    }

    /** main: creates the object and calls the methods. */
    public static void main(String args[])
    {
        SumDigits ob = new SumDigits();   // object of the class
        ob.accept();
        if (ob.n >= 0)                    // a negative number is not accepted
        {
            ob.total = ob.sumDigits(ob.n);
            ob.display();
        }
        else
            System.out.println("Invalid input: enter 0 or a positive number");
    }
}

Variable description table

Sample input and output

Enter a number (0 or more): 2947
Sum of the digits of 2947 = 22

Enter a number (0 or more): 0
Sum of the digits of 0 = 0

Enter a number (0 or more): 5
Sum of the digits of 5 = 5

Enter a number (0 or more): -45
Invalid input: enter 0 or a positive number

Dry run

Take $n = 2947$. sumDigits(2947) is called. The calls go down until num is 0, then the values return up.

Returning up: 0, then 2 + 0 = 2, 9 + 2 = 11, 4 + 11 = 15, 7 + 15 = 22. total becomes 22 and the program prints Sum of the digits of 2947 = 22, the same as the first sample run.

Variations

1. Sum of digits using a loop "Write a program to find the sum of the digits of a number using a loop."
2. Reverse a number "Using recursive technique, find the reverse of a number."
3. Power function "Using recursive technique, find x raised to the power n."
4. Repeated addition "Keep adding the digits of a number until a single digit is left."