Recursion program trouble... ?

This is a discussion on Recursion program trouble... ? within the C Programming forums, part of the General Programming Boards category; My first recursion program. Qs: To calculate the sum of digits of a 5 digit number using recursion. I can ...

  1. #1
    Registered User
    Join Date
    May 2008
    Posts
    16

    Recursion program trouble... ?

    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?

    Code:
    #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);
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,303
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    993
    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:
    Code:
    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:
    Code:
    #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.

  4. #4
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    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.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by slingerland3g View Post
    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.)

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    The function rec can be done in just one statement.
    Code:
        return (d > 9) ? rec(<something>) + <something> : <something>;
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by slingerland3g View Post
    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!

  8. #8
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Ah!, Good ol' modulus. Thanks

    Code:
      while(z >= 1)
        {
          digit = (number/z) %10;
          sum += digit;
        
          z /=10;
        }
    The sum of number(56724) = 24

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with my program...
    By Noah in forum C Programming
    Replies: 2
    Last Post: 03-11-2006, 07:49 PM
  2. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 07:39 AM
  3. Replies: 2
    Last Post: 05-10-2002, 05:16 PM
  4. big trouble in little program
    By jonesy in forum C Programming
    Replies: 1
    Last Post: 10-04-2001, 03:04 PM
  5. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 11:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21