Sum of Digits using recursion in C

Question

For our activity today, we were tasked to make using recursion with the sum of digits. I already made this program:

int main()

{
int num = 0, sum;

printf("Enter an integer: ");
scanf("%d",&num);

//counter=1;

for ( sum=0; num>0;)

{
    sum = sum + num % 10;
    num = num /10;
  }
printf("Sum = %d", sum);

getch();
return 0;

}

Our teacher added "Input and output must be done in the main() function." Am doing the right thing? Or am I missing something in my code?

Answer 1

What you have there is an iterative solution, not a recursive one.

Recursion involves defining the problems in terms of a simpler version of the problem, all the time working towards a fixed end point.

The fixed end point in this case is any number less than 10, for which the value is that digit.

The transition to a simpler case (for numbers greater than 9) is simply to add the least significant digit to the result of the number divided by ten (integer division).

Since it's classwork, pseudo-code only I'm afraid.

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

If you follow that for the number 314, you'll see what happens.

• At recursion level one, n == 314 so it calculates 314 % 10 to get 4 and calls digitSum(31).
  • At recursion level two, n == 31 so it calculates 31 % 10 to get 1 and calls digitSum(3).
    • At recursion level three, n == 3 so it just returns 3
  • Back up to level two, that's added to the remembered 1 and returned as 4.
• Back up to level one, that's added to the remembered 4 and returned as 8.

Hence you end up with the digit sum of 8 for the number 314.

Answer 2

To do recursion, create a function that recurses rather than using a for loop.

int SumDigits(int i) {
  if (i < 10) {
    return i;
  }
  else {
    return i%10 + SumDigits(i/10);
  }
}


scanf("%d", &i);
printf("%d\n", SumDigits(i));