Go Program for Sum of Digits Using Recursion

In Go, you can find the sum of digits using recursion by defining a function like func sumDigits(n int) int that returns 0 if n == 0, otherwise returns n % 10 + sumDigits(n / 10).

Examples

Input123

Output6

Input0

Output0

Input9999

Output36

How to Think About It

To find the sum of digits using recursion, think of breaking the number into its last digit and the rest. Use n % 10 to get the last digit and n / 10 to remove it. Keep adding the last digit to the sum of digits of the remaining number until the number becomes zero.

Algorithm

1

Check if the number is 0; if yes, return 0.

2

Find the last digit using modulo 10.

3

Call the function recursively with the number divided by 10.

4

Add the last digit to the result of the recursive call.

5

Return the sum.

Code

go

package main

import "fmt"

func sumDigits(n int) int {
    if n == 0 {
        return 0
    }
    return n%10 + sumDigits(n/10)
}

func main() {
    num := 12345
    fmt.Println("Sum of digits:", sumDigits(num))
}

Output

Sum of digits: 15

Dry Run

Let's trace sumDigits(123) through the code

1

Initial call

n = 123, n != 0, last digit = 3, call sumDigits(12)

2

Second call

n = 12, n != 0, last digit = 2, call sumDigits(1)

3

Third call

n = 1, n != 0, last digit = 1, call sumDigits(0)

4

Base case

n = 0, return 0

5

Return from third call

return 1 + 0 = 1

6

Return from second call

return 2 + 1 = 3

7

Return from initial call

return 3 + 3 = 6

Call	n	Last Digit	Recursive Call	Return Value
sumDigits(123)	123	3	sumDigits(12)	6
sumDigits(12)	12	2	sumDigits(1)	3
sumDigits(1)	1	1	sumDigits(0)	1
sumDigits(0)	0	-	-	0

Why This Works

Step 1: Base Case

The function stops calling itself when the number becomes 0, returning 0 to end recursion.

Step 2: Extract Last Digit

Using n % 10, the function gets the last digit of the number to add to the sum.

Step 3: Recursive Call

The function calls itself with the number divided by 10, removing the last digit, to process the remaining digits.

Step 4: Sum Calculation

Each call adds the last digit to the sum returned by the recursive call, building the total sum step by step.

Alternative Approaches

Iterative approach

go

package main

import "fmt"

func sumDigitsIterative(n int) int {
    sum := 0
    for n != 0 {
        sum += n % 10
        n /= 10
    }
    return sum
}

func main() {
    fmt.Println("Sum of digits:", sumDigitsIterative(12345))
}

This uses a loop instead of recursion, which can be easier to understand and avoids function call overhead.

String conversion approach

go

package main

import (
    "fmt"
    "strconv"
)

func sumDigitsString(n int) int {
    s := strconv.Itoa(n)
    sum := 0
    for _, ch := range s {
        sum += int(ch - '0')
    }
    return sum
}

func main() {
    fmt.Println("Sum of digits:", sumDigitsString(12345))
}

This converts the number to a string and sums digits by converting characters back to integers, which is simple but less efficient.

Complexity: O(log n) time, O(log n) space

Time Complexity

The function processes each digit once, and the number of digits is proportional to log base 10 of n, so time is O(log n).

Space Complexity

Each recursive call adds a layer to the call stack, so space used is proportional to the number of digits, O(log n).

Which Approach is Fastest?

The iterative approach uses O(1) space and is generally faster due to no function call overhead, but recursion is elegant and easy to understand.

Approach	Time	Space	Best For
Recursive	O(log n)	O(log n)	Learning recursion, simple code
Iterative	O(log n)	O(1)	Performance and memory efficiency
String Conversion	O(log n)	O(log n)	Simple code, less math