Recursive Function Help...

[chaoz014]

So this is my second project in C++, but I'm having some trouble understanding Recursive functions.

We are supposed to write a program that has a recursive function. And the program should ask the user for a number. And then display the number of even digits that the number had.
ie. input: 22378
output: the number had 3 even digits on it

So far this is my code, but I'm having lots of trouble with the recursive

#include <iostream>
using namespace std;

int howManyEven (int);

int main (){
	
	int number, again = 1;

	while (again == 1){
		
		cout << "Please enter any number: ";
		cin >> number;

		cout << "Your number had " << howManyEven(number)  << " even digits on it. \n";
	
	
		cout << "Want to do it again? (1) = YES (0) = NO: ";
		cin >> again;
	
	}
	return 0;
}

int howManyEven(int n){
	if (n%2 == 0)
	return 1;

	return howManyEven(n/10);
	


}

[WaltP]

Where are you adding the number of evens? All I see is you returning 1.

Also, you aren't breaking out of your recursion.
You test if n is even and return 1.
If n is odd, you call the function again.
But you don't count the evens, and you don't exit/return if you run out of digits.

What you need to do is call the function like you do with your n/10
When n enters as zero, start your return cycle.
If value is even, count it
Return the count.

[Fortran IV]

Okay, I’ll start on my soapbox. I’m not a fan of recursion. It tends to be difficult to add features and enhancements to recursive code without breaking it. Of course, this is not a concern for a student project. Also, recursive code is most applicable to applications that have arbitrary data. Unfortunately, truly arbitrary data can break most recursive programs! Recursive programs have the ability to suck up every available system resource. (You would be amazed how fast an errant recursive program can fill a 750MB hard drive!) With that said, let me give you some general suggestions on recursive code:

What a recursive function does is several things: It looks at some data, and based on the data, either calls itself again, or exits back. In either case, it may do some processing on the data (counting, parsing, averaging, etc.), or it may not. When it calls itself, it will (hopefully) be looking at some different data.

Think of a recursive program as kind of like exploring a cave. You get to a point where the tunnel splits, you pick a side, and you go on until that path splits or ends. If it splits, you chose a side and follow it. If it ends, you go back to the previous split and take the next path. Eventually, you will have reached the end of every tunnel, and you can head back out, carrying the treasures that you found at the ends of the tunnels.

First and foremost, you need to have a way of deciding when you are at the end of a tunnel. Every recursive function MUST have a way of returning a value that breaks it out of recursion. This is what WaltP was referring to. A recursive function has to either return (that is, the program’s execution goes back to where the function was called) or it calls itself again. Beginning programmers tend to focus on the “Call Again” part and ignore the “Exit” part. Oh, and when it returns, it should to be returning a value that indicates that it reached an end. This is analogous to putting a marker at the entrance to each tunnel so that you don’t go back down one you already explored.

The second thing is that the function has to process the data. This may be as simple as writing a number to a console, or saving a value in an array. The important thing to keep in mind is the scope of the storage. It either has to be saved at the level of the “Main” function, or the value has to be carried all the way back. If you write values to a console, obviously that is the ultimate in “global” storage, and you don’t need to worry about storage scope.

The third thing is that something has to be different when you make each recursive call. In other words, the data that is being evaluated has to be different every time. Otherwise, you end up in an endless loop.

So, let’s apply this to your problem. In the Main read in the data, and call the recursive function. In the recursive function, first look at the data. Do some evaluation. Is there data? Is the length of the number greater than 0? [You did not specify whether this program had to handle negative numbers.] If not, you are done. End of tunnel. Return back (First point). If there is data, do some processing. In your case, look at one digit of the number, and decide if it is odd or even. [Hint: You can test if the entire number is odd or even, and that will tell you if the least significant digit is odd or even.] (Second point) Modify the data by getting rid of the least significant digit (Your “n/10”). Call the function again with the new data. (Third point).

Going back to saving the data: I would probably increment counts at the Main level for both odd and even digits. I suspect your instructor wants you to be more clever. In this case, code the function so that if it detects an even digit, to return a value of 1 plus whatever value was returned from next (downstream) recursive call. If it detects an odd digit, just return the value from the next recursive call. This will cause it to sum up the digits. Incidentally, I would actually keep track of odd digits rather than even digits. There is a reason for this, but I’ll leave that for you to figure out.

It is always good practice to keep track of how many levels deep your recursion has gone. You can just pass a counter in the function call. Start it at ‘0’ when the function is called from Main. Increment it in the recursive function, and pass it along on the next call. If it gets too large, flag that as an error, and exit out of the recursive function (and keep exiting all the way back to the Main. You should code this up this first. It will help with debugging. It might not be a bad idea to print out this count, along with the data, and whether the number is odd or even in the function. Again, this will help with debugging.

This solution is suitable for a “linear” or “one dimensional” recursion problem. That is, a problem where the decision is either to go to the next level or to stop. There is only one path, and the path may be longer or shorter depending on the input data. For branching recursion, like what you might use for factoring a number, a slightly different method must be used. In branching recursion, at each level you may have to go down one recursive path, return, and then go down another path. For this type of problem, you would more typically have your recursive function return a value indicating if it had reached the end of a path, rather than the data.