Solving C++ Recursion Problem with Summing Digits

[Math Is Hard]

Hi,
I am playing around with doing stuff recursively, just to practice, and I have a problem I can't work out. I want to write a recursive function that will sum the digits of a number, take the result, sum those digits, etc. until I reach a single digit number. Then I want to return that single digit number from my function.
In other words, if I start with number 4322:

4322 => 4+3+2+2 = 11,
11 => 1+1 = 2
so 2 is the number I want to return

What I've been able to do so far is write a little program that goes through one iteration of summing the digits. I know that when I make the function I'll need to pass the sum back to the function, and I think my stopping condition will be when the number passed in is a single digit, but I'm still not sure how to set this all up. Any help is appreciated. Thanks.

# include <iostream>
using namespace std;

int main()
{
	int n = 4322;
	int sum = 0;
	while (n > 0)
	{
		sum = sum + n%10;
		n = n/10;	
	}
	cout << sum <<endl;
	return 0;
}

 

[gnome]

If you want to do it recursively, the action shouldn't be in main. Put it into a separate function that is called by main, and that can call itself.

The first line of that function should test for the stopping condition.

Do you want more, or do you want to work on it yourself?

 

[gerben]

You should have a function that adds the digits and calls itself as long as the required endpoint is not reached, when the endpoint is reached it should return.

Here is an example in white:

[COLOR=black]void main ()
{
  int n = 4322;
    
  f(n);  
}

int f(int n)
{
    int sum = 0;

    if (n == 0)
        return 0; 
    else if (n/10 == 0)
    {
        cout << n << endl;
        return 0;
    }
    else
    {
        while (n > 0)
	{
	    sum = sum + n%10;	  
            n = n/10;	
	}
        f(sum);
    }
}[/COLOR]

 

[faust9]

Your final test shoud be something like n>10 or n<10 depending on how you code your functions.

The first thing you want to do is to pull the function you wrote out of main and into an independent function definition:

# include <iostream>
using namespace std;

int main()
{
	int recCountDown(int);
	recCountDown(4322);
}

int recCountDown(int n);
{
	int sum = 0;
	while (n > 0)
	{
		sum = sum + n%10;
		n = n/10;	
	}
	cout << sum <<endl;
	return sum;
}

This in and of itself does not answer the problem recursively (actually this lends itself to inline programmin which is more efficient) but this is typically how you deal with functions in c/c++. You put them in their own files or outside of main when possible.

To use recursion simply decide on a test criteria (n>10) and write a loop within the recursive function which calls the recursive function.


Now, do you really need to do this using recursion? No, and in all actuality you probably wouldn't want to if this where a real program. Recursive functions have this nasty tendency to get real big and bloated really quickly and as such should be avoided unless absolutely positively necessary. The above program would work very well using a simple while loop in main calling the digit counting function several times until all digits have been summed to less than 10.

The non-recursive form--good luck with recursion.

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
	int recCountDown(int);			//lets compiler know a function is outside of main
	int someNumberToPass=4332;		//single location for number to be parsed
	int testCase=someNumberToPass;		// sets up a testcase to end the while loop
	while(testCase>10){			//inline loop to sequentially sum the digits of a number
	testCase=recCountDown(testCase);
	}
	cout << testCase <<endl;
}


//function used to sum the digits of a number
int recCountDown(int n)
{
	int sum = 0;
	while (n > 0)
	{
		sum = sum + n%10;
		n = n/10;	
	}
	return sum;
}

Hope this helped a little.

[edit]I want to clarify something. You are not allowed to write a function within a function but you can get away with writing the contents (the meat and potatoes if you will) of a function within a function. If you have code that looks like a function then define it as such.

 

[Math Is Hard]

Thanks very much, gerben and faust - yes, that helped a lot. I'm just trying to learn recursion, so I am trying to think of things I can do with it for practice - even if recursion is not the best way to go about it.
And yes - my plan was to put everything into a separate function, not in main(), when I had the strategy figured out. I just posted the program I had written in main() to show you I had tried to work on some of the functionality. I thought it would be rude to just post "Hey - show me how to do this!"
A few other things I've been doing for practice are creating functions for: computing a number at a position in a Fibonacci sequence, a recursive power function, and a factorial function. If you can think of any other simple things I might try for practice I would be glad to hear your ideas. Thanks.

 

[gerben]

Basically anything that requires you to perform the same action again and again until some required end state is reached. I think one of the simplest examples could be integer division. If you want to divide M by X you just do M -= X until M < X. (oh eh yeah this works only for positive numbers of course)

 

[gnome]

Implement your own add, subtract, multiply, divide functions.

Reverse a string.

Binary search (search for an element in an array).

In case anyone's interested, here's an implementation of your sum-of-digits program in Prolog:

sum_dig(0,0).
sum_dig(N,S) :-
        Q is N // 10,
        R is N mod 10,
        sum_dig(Q,S1),
        S is R + S1.

Really. That's the whole program.

 

[gerben]

Wow that is short, in C/C++ a recursive factorial function can be written very short:

int fact(unsigned int n) 
{
  return (n <= 1) ? 1 : n * fact(n-1);
 }

 

[gnome]

Nice. Here's another cute one. Remember quicksort? I remember agonizing over writing that partition function in C. Well here's quicksort written in Haskell (needless to say, I didn't invent it; just thought people would get a kick out of it):

quicksort [] = []
quicksort (x:xs) = quicksort[y | y <- xs, y < x]
                    ++ [x]
                    ++ quicksort[y | y <- xs, y >= x]

That's the whole thing. No #include, no using ... , etc.

 

[faust9]

Thanks very much, gerben and faust - yes, that helped a lot. I'm just trying to learn recursion, so I am trying to think of things I can do with it for practice - even if recursion is not the best way to go about it.
And yes - my plan was to put everything into a separate function, not in main(), when I had the strategy figured out. I just posted the program I had written in main() to show you I had tried to work on some of the functionality. I thought it would be rude to just post "Hey - show me how to do this!"
A few other things I've been doing for practice are creating functions for: computing a number at a position in a Fibonacci sequence, a recursive power function, and a factorial function. If you can think of any other simple things I might try for practice I would be glad to hear your ideas. Thanks.

Write a recursive function to calculate points on a mandelbrot set(it's easier than it sounds). Use C++ to find these points and store them in a comma separated file. Use excel or gnuplot or something like that to plot the points.

The real exercise is to write the mandelbrot recursive set function.

The next exercise is formatting the output and sending it to a file for future use(very very important concept--moreso than recursion IMHO).

Then use whatever pgm you are comfortable with to see the result.

Personally, I feel if you understand what recursion is and can write "simple" recursive functions then you're good for now. As I said already, recursive functions can usually be written as inline functions which do not grow exponentially like recursive functions do. Recursive functions have their place for sure but beginners are better served trying to aviod them than to master them.

Writing code for a pentium or PPC based system will show little change between a recursive or non-recursive form; however, programming something like an HC11F1 (motorola microcontroller) will.

 

[Math Is Hard]

Recursive functions have their place for sure but beginners are better served trying to aviod them than to master them.

I totally agree with you! I can't believe this class is called "Introduction to Programming" but I'm going to have to write a recursive function on my test tomorrow. I am trying to study everything I possibly can to prepare, because I have no idea what will be thrown at us. I'm really worried!

p.s. gerben, that tiny little factorial computing function was so cool! wow!
p.p.s. Inspired by that, I tried to write a tiny little recursive function for finding a power from a base and exponent when the exponent is zero or larger (not completely accurate since I'm using unsigned versions for negative numbers that could be input):

int power(unsigned int base, unsigned int expo) 
{
  return (expo ==0) ? 1 : base * power(base,expo-1);
}

 

[gnome]

Neat!

But watch out: some professors get pissed off when you use conditional expressions. They say it detracts from the program's readability.

(But I say, hey, that's what makes it fun. )

 

[Math Is Hard]

The weird thing is - my prof actually likes conditional expresions. I was surprised to find this out because my textbook book barely covers them calling them "archaic" and "not-recommended" and such.

 

[gnome]

Different strokes ...

Like some people have an aversion to recursion. I have to admit I was one of them when I was first introduced to it. But now, I think it's almost as much fun as ...

wellllll, maybe not THAT much fun.

 

[Math Is Hard]

But now, I think it's almost as much fun as ...

a root canal? :rofl:
at the moment, that would be my comparison! (but that's just because I have a test tomorrow)

 

[gnome]

Guess it's an acquired taste.

At this point probably your best preparation is a good night's sleep. Good luck on the test.

 

[Math Is Hard]

thanks, gnome. I think you're right (yawn).

 

[The Idiot]

I like recursion... Right now I have to write something that I'm told will use double recursion... (A recursive function that will call another recursive function that may call the first one again, etc.)