Recursion program trouble... ?

[Beachblue]

My first recursion program.
Qs: To calculate the sum of digits of a 5 digit number using recursion.

I can do it using functions. But the recursion way is not working. I admit, I did a lot of guess work and trial and error, but it did seem logical. Can you tell me where I'm wrong?

#include<stdio.h>

int main(void)
{
      int d, sum, num;

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

      sum=rec(d);                         /* Here I get an error saying I haven't declared 'd', but I                 
                                                       have. */

      printf("\nSum is %d", sum);
      getch();
      clrscr();
}

rec(d)
int d, num;                                 /* Is this allowed? I did this because I didn't want the 
                                                      rec to affect  num */
{
      int digit, s=0;

      d=10000;

      while(d>=1)
      {
           digit=(num/rec(d/10))%10;
           s=s+digit;
      }

      return(s);
}

[laserlight]

Can you tell me where I'm wrong?

It looks like you have a syntax error in your attempt to use an old way of declaring parameters of a function.

Before you start to code, I suggest that you work out the base case of the recursion and the recursive step.

[cas]

You appear to be trying to mix both iteration and recursion. The whole looping bit looks like it might be an adaptation of earlier code you used, with recursion shoehorned in there. The idea with recursion here is that the problem can be broken down into a number of steps that are all similar.

First things first: Your declaration of rec() is not correct. First, if you create a variable called "num" inside of rec(), it will be different from the variable called "num" in main(). Next, you should use a prototype, such as:

int rec(int d)

You want to tell the compiler what rec() returns, and the type of its argument. You're also assigning to d in your rec() function, which doesn't make sense, because d already has the value that's been passed into it. There's no point in passing in a value if you immediately reassign it.

To recursion, then. I'll try to give a clear example using a tried-and-true recursion exercise; namely, factorial. Hopefully when you see how the factorial program works, you'll have a better idea of how to break down your problem and implement it.

As I'm sure you're aware, the factorial of a number n (denoted n!) is the product of all integers from 1 to n, inclusive. 5! is 5 * 4 * 3 * 2 * 1 = 120. This lends itself easily to recursion once you notice that 5! is the same as 5 * 4!, and 4! is the same as 4 * 3!, and so on. Thus the factorial of any number n is n * (n - 1)! as long as n > 1. Technically it'd work for n == 1, but I'm pretending for now that 0! doesn't exist to simplify things.

One important thing in recursion is that you have what's called a base case; that is, at least one input to your recursion function must cause it not to call the function again, or you'll never return from it! In our case, we can say that an input of 1 will be the base case, and 1! is just 1. So it goes something like this:

#include <stdio.h>

unsigned long fact(unsigned long n)
{
  if(n == 0) return 1;    /* 0! is defined to be 1, so take care of that. */
  if(n == 1) return 1;    /* This is the base case: once we ask for 1!,
                           * the result is simply 1; no need to calculate.
                           */

  return n * fact(n - 1); /* n * (n - 1)! */
}

int main(void)
{
  printf("%lu\n", fact(5));
  printf("%lu\n", fact(10));

  return 0;
}

So for your problem, see if you can break it down into steps like I did with factorial here, and then implement the solution in a similar fashion.

[slingerland3g]

Good cas,

But I wonder if the issue is really to split this 5 digit number and then add them all up. Example

56724 = 24

In that case this digit will need to be read in as a string and spit the string and convert to each to an int to sum up. Or possibly read in as a binary and bit shift. There are a few ways to perform that.

[tabstop]

Good cas,

But I wonder if the issue is really to split this 5 digit number and then add them all up. Example

56724 = 24

In that case this digit will need to be read in as a string and spit the string and convert to each to an int to sum up. Or possibly read in as a binary and bit shift. There are a few ways to perform that.

But ... but ... splitting one digit off the rest of the number was the only part the OP got right? (Or, at least, the most right.)

[iMalc]

The function rec can be done in just one statement.

    return (d > 9) ? rec(<something>) + <something> : <something>;

[Adak]

Good cas,

But I wonder if the issue is really to split this 5 digit number and then add them all up. Example

56724 = 24

In that case this digit will need to be read in as a string and spit the string and convert to each to an int to sum up. Or possibly read in as a binary and bit shift. There are a few ways to perform that.

Not at all, it's a base 10 number system, and he's successively applying mod to each left over number, after dividing it by *tada* 10!

[slingerland3g]

Ah!, Good ol' modulus. Thanks

  while(z >= 1)
    {
      digit = (number/z) %10;
      sum += digit;
    
      z /=10;
    }

The sum of number(56724) = 24