Recursion UGH!

I have never been good at thinking recursively - when studying JAVA, C and now again studying C++. Not that I am good at anything right now as a student but, I have tripped over it every time. It is assigned again, and I have to do it.

There were three assignments. The first was drawing a picture of stars. I got through that with great difficulty, and now I am tripping myself up with the next two and confusing the beegeebers out of myself. They are:

1. Writing a recursive function, vowels, that returns the number of vowels in a string, then write a program to test the function.

2. Write a recursive function to check whether a string is a palindrome or not. The function returns true or false and I can't use any global variables.

Focusing on the first, I can do it with a for loop checking each position in the string if it matches a vowel in caps or lower case and incrementing a counter if it does, otherwise just moving to the next position but recursively ...not.
I have an algorithm that:
1. asks for a string.
2. sends the string to the function (I think i need to send a pointer, too)
3. checks the first string position against the list of vowels
4. if found increment counter, move to next position
if not just move to next position
5. repeat 4 until end of string is reached
6. return counter

But, how do I put this into a recursive function???
My main looks like:

Code:

#include <iostream>
#include <string>

using namespace std;

void displayBanner();
int vowels(string phrase, int count);

int main()
{
	int ptr = 0;
	displayBanner();
	cout << "Enter a phrase: ";
	string phrase;
	getline(cin, phrase);
	cout << "\nThe phrase you entered: " << phrase << endl;
	cout << "\nhas " << vowels(phrase, ptr) << " vowels." << endl;
	return 0;
}

void displayBanner()
{
	cout << "This programs asks for you to enter a string.\n"
		 << "it then calculates how many vowels it contains\n"
		 << "using a recursive function.\n\n";
}

and so far my recursive functio is a mess, but is:

Code:

int vowels(string phrase, int *ptr)
{
	while (phrase[i] != '\n')
	{
        if (phrase[i] == 'a' 
			|| phrase[i] == 'e' 
			|| phrase[i] == 'i' 
			|| phrase[i] == 'o' 
			|| phrase[i] == 'u' 
			|| phrase[i] == 'A' 
			|| phrase[i] == 'E' 
			|| phrase[i] == 'I' 
			|| phrase[i] == 'O' 
			|| phrase[i] == 'U')
			count++;

		vowels[i + 1];
	}
	return count;
}

Am I moving it the right direction, or do I need to scrap the function and rethink everything?
By the way, I search this board for help before posting and I couldn't find anything that helped me.
Thanks for the help ALL.

Not related to recursion

Code:

while (phrase[i] != '\n')

Is there any reason to believe the string would end with a newline (not, unless you put it there). Use the size() method to find out the length.

As to recursion.
Recursion is supposed to break a task into similar subtasks. So in this case at each depth of recursion you would check one character and then pass the rest of the task on recursively.

Supposing this function would return the count of vowels, you'll have something like this somewhere:

Code:

    count += countVowels(the_string, pos + 1);

Thanks for the info, I will work on what you suggested anon, and see where that gets me.
I just seem to think myself recursively into an infinite hole, well until I run out of memory (a recursive joke sort of, the only one I get actually).

Nope! Still not getting it.
I understand I have to check the first position in the string, then call the function again, to check the next position, and so on to the end, then return the count of vowels, but I am not getting the code part of it.
This is so frustrating!!!

May-be you could post what you have now?

I understand I have to check the first position in the string

I suppose, not first - the position that you were told to check when the function was called.

I still can't figure out how to count the vowels.
This is what I have so far, but because count isn't declared properly, I don't even know if it works!

Code:

#include <iostream>
#include <string>

using namespace std;

void displayBanner();
int vowels(string phrase);

int main()
{
	int ptr = 0;
	displayBanner();
	cout << "Enter a phrase: ";
	string phrase;
	getline(cin, phrase);
	cout << "\nThe phrase you entered: " << phrase << endl;
	cout << "\nhas " << vowels(phrase) << " vowels." << endl;
	return 0;
}

void displayBanner()
{
	cout << "This programs asks for you to enter a string.\n"
		 << "it then calculates how many vowels it contains\n"
		 << "using a recursive function.\n\n";
}

int vowels(string phrase)
{
	if (phrase.size() >= 1)
	    if (phrase[0] == 'a' 
			|| phrase[0] == 'e' 
			|| phrase[0] == 'i' 
			|| phrase[0] == 'o' 
			|| phrase[0] == 'u' 
			|| phrase[0] == 'A' 
			|| phrase[0] == 'E' 
			|| phrase[0] == 'I' 
			|| phrase[0] == 'O' 
			|| phrase[0] == 'U')
			count ++;

	phrase[0] = phrase[phrase.length() - 1];
	return count;
}

How can I initialize count inside the function without resetting it every time through the function? I can't use a global variable.
And this obviously WON'T work because I am not even calling the function!!!
UGH!

The trick with recursion is to think about the problem and its solution in a very different manner. What you want to do is think of how the problem can be solved simply in part by itself.

One commonly used example of recursion and how it works is to consider factorial numbers. A factorial of a number n is simply defined as n * n-1 * n-2 .... 1.... So the factorial of 2 is 2, 3 is 6, 4 is 24, etc. etc.. Simple written:

2! = 2
3! = 6
4! = 24

Now you can do it iteratively:

Code:

int i_factorial(unsigned int n)
{
	int ret = 1;
	while(n > 1)
	{
		ret *= n;
		n--;
	}
	return ret;
}

Or you can do it recursively:

Code:

int r_factorial(unsigned int n)
{
	if(n <= 1)
	{
		return 1;
	}
	else return n * r_factorial(n-1);
}

Being forced to write recursive functions atm, you should get into the recursive mindset. Here's how you would take the factorial task.

Iteratively:

1. You must use a loop.
2. As a result of the previous requirement, you need at least one loop condition that signifies you're finished processing the data.
3. You realize that your loop condition in this case ends when n is 1 (or possibly 2 with multiple cases, but we'll consider 1 to be the final case for now for simplicity).

Recursively:

1. You do NOT need a loop in the traditional sense, but the function calls will server as a loop.
2. As a result of this sort of loop, you need at least one condition to stop it. This condition is called a base case.
3. You realize that the number passed to your function stops when you know the answer and can't go any further, in which case, this is 1.

You can clearly see both methods are doing the same thing:

1. They both need a loop or a way to repeat.
2. They both have a condition of sorts to stop this repetition.
3. Once you have the condition you're set.

Iterative vs Recursive matters a lot about how you look at it:

Which definition do you see as closer to your preferred way of thinking about it?

Code:

5! = 5 * 4 * 3 * 2 * 1

Code:

5! = 5 * 4!

I know I went off on a long tangent with a problem you're not doing, but my goal is to help you understand recursion a little better. Once you get passed whatever is making it difficult, you will be able to use it for many other problems.

In your case, for the vowels, you are correct that you need to go through them all, but you need to stop thinking of the entire project at once. Think of whatever base cases you need. How would you handle one char? How would you handle an empty string?

Can you define your function like the factorial? How do you see the vowels function? Which one of the following ways do you prefer to think about it?

Code:

vowels("test") = 0 + 1 + 0 + 1

Code:

vowels("test") = 0 + vowels("est")

Both work. To write it recursivly, though, you need to think of it in terms of the last one.

I get what you are saying and how you are explaining what needs to be done, however...making my brain reset and think in a different way is the BLOCK.
I learned programming with procedural languages a long time ago. Now as a student again the languages are object-oriented. I went through C and that was ok, then I took JAVA, I about died with the objects, next was C++ I was gettting the objects better, and now with DataStructures in C++ I GET the objects, finally! But I haven't been able to get the recursive thinking mindset yet. Old Dog I guess, and there isn't a big enough bone so far!!!

I want to get it, I just can't seem to twist my mind to get there yet.

OK, then let's start out slow.

Steps to complete the recursive function:

1. Write out skeleton of function.
2. Determine all necessary base cases.
3. Add them into the code.
4. Determine all remaining recursive calls.
5. Add them into the code.
6. Go enjoy a pizza with a good soft drink.

I'll start you off with step one:

1. Writing a recursive function, vowels, that returns the number of vowels in a string, then write a program to test the function.

Code:

int vowels(string s)
{

}

Fair enough? We want to receive a string and return the number of vowels in it.

Now step 2 is to determine the base cases. The base cases are the conditions that cause us to stop repeating. It's akin to stopping a loop by way of a loop condition. What exactly are the conditions that we can tell to actually stop? How can you tell when you're supposed to stop counting characters? (Yes, it's this basic. Really.).

Now all you have to do is check exactly for that.

Base Cases:
string is empty, or at the end of the string. Right!
so, that would be s.empty() and s[0] == s.size()-1

You can actually just check if the string is empty. You don't have to check if you're at the end per se. So if the string is empty, how many vowels are in an empty string? Whatever your answer is, return that.

You have your base case. So now simply add it to the code and complete step 3.

Now move to step 4. If the string is NOT empty, what do you do with it? Slight hint.... Similar to the recursive factorial function I posted, you want to do a partial analysis of the string and pass most of it to the next layer of recursion.

I've been working on that one. But this is the really hard part for me.
I know that I have to increment a count for the vowel found if one then add it to the recursive call of the string at position [0 + 1]. I just don't know how to put that together.

I feel like such a hard head on this. It is really embarrassing.

this is my function so far, but I can't figure out the "counter"

Code:

int vowels(string phrase)
{
	if (phrase.empty())
		return 0;
	if (phrase[0] == 'a' 
		|| phrase[0] == 'e' 
		|| phrase[0] == 'i' 
		|| phrase[0] == 'o' 
		|| phrase[0] == 'u' 
		|| phrase[0] == 'A' 
		|| phrase[0] == 'E' 
		|| phrase[0] == 'I' 
		|| phrase[0] == 'O' 
		|| phrase[0] == 'U')
	return	counter +  vowels(phrase.size()-1);
}

I am really sorry to not 'get' this as I should.

Well, usage of counter is wrong. You have to remember that the functions are internally keeping track without you explicitly telling it. You're still thinking iteratively. More on this later.

What you're passing to vowels is wrong. You should be passing a string, not an int. phrase.size() is an int, and you're just passing it one less. You need to pass the same string you received except it's missing it's first char. That's it. Look up the erase() function in std::string in order to get rid of the first char. Others that know C++ alot better than me might have a more common way to do that.

Now back to counter. You have to realize this:

Code:

vowels("test") = 1
vowels("ing") = 1
vowels("testing") = 2
vowels("test") + vowels("ing") = 2

The beauty of this is that when you call vowels() again in your function, you automatically know it will return the exact number of vowels in the string. You don't need to have any counter. If you have a vowel in phrase[0], how many vowels exactly is that? And how many more do you have in your string? Do you even need to know? No, you don't. All you have to do is handle the first char and then rely on the function to figure out the rest.

If you've properly picked up everything I said, you should be able to complete this function after reading this post.

The operative word is SHOULD!!!
I will read and reread until I 'get' it. I hope I 'get' it.
Thank you, MacGyver for your time and extreme patience!
I appreciate it. And will have this done before I sleep, I hope!
Since I have been working on this ALL day! And have one more after this one.
Double UGH!

You're actually almost there. If you have any questions, though, ask.

The palindrome one is very similar to this in some ways.