C++

Forum

 
 
Recursive vs Iterative

enilc (5)
This is my first post to this website. If I am failing to abide by any rules, please let me know, so that I will not do it again.

I am working on a homework problem for class. I am writing a function called vowels that is supposed to count the number of vowels in a given string. The function is supposed to work recursively. I believe my function does so, but I am looking for confirmation from a more experienced programmer. Any help on my learning path is greatly appreciated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 

#include <iostream>
#include <string>

using namespace std;

double vowels (string myString)
{

double vowelCount;
int count;
int strLength = myString.length();

vowelCount = 0;
count = 0;

while (count < strLength)
{
	if (myString[count] == 'A')
	{
		vowelCount = vowelCount + 1;
		count = count + 1;
	}
	else
		if 	(myString[count] == 'E')
		{
			vowelCount = vowelCount + 1;
			count = count + 1;
		}
		else
			if	(myString[count] == 'I')
			{
				vowelCount = vowelCount + 1;
				count = count + 1;
			}
			else
				if (myString[count] == 'O')
				{
					vowelCount = vowelCount + 1;
					count = count + 1;
				}
				else
					if 	(myString[count] == 'U')
					{
						vowelCount = vowelCount + 1;
						count = count + 1;
					}
					else
						if 	(myString[count] == 'a')
						{
							vowelCount = vowelCount + 1;
							count = count + 1;
						}
						else
							if 	(myString[count] == 'e')
							{
								vowelCount = vowelCount + 1;
								count = count + 1;
							}
							else
								if 	(myString[count] == 'i')
								{
									vowelCount = vowelCount + 1;
									count = count + 1;
								}
								else
									if 	(myString[count] == 'o')
									{
										vowelCount = vowelCount + 1;
										count = count + 1;
									}
									else
										if 	(myString[count] == 'u')
										{
											vowelCount = vowelCount + 1;
											count = count + 1;
										}
										else
											count = count + 1;
}
return vowelCount;
}

int main()
{
double vowelTotal;
vowelTotal = vowels ("This is a test.");
cout << "Vowel Count: " << vowelTotal << endl;

return 0;
}
Last edited on
shamieh (161)
A recursive function is a function that calls itself. You are using if/else statements..

http://www.cplusplus.com/articles/D2N36Up4/

Also, as far as good formatting, it should be written like this:

1
2
3
4
5
6
7
8
9
10
 
if(stuff)
  do stuff
else if(stuff)
  do stuff
else if(stuff)
  do stuff
else if(stuff)
  do stuff
else
  done


So try to use that instead of the stairs method.. i.e. --> 
1
2
3
4
5
6
 
 
                                                                                 stuff
                                                                                         do stuff
                                                                                                walking  
                                                                                                       down
                                                                                                            stairs
Last edited on
kevinkjt2000 (1063)
The classic example for recursion is usually factorial, since that is typically a familiar mathematical function. Regardless of what the recursive function is supposed to do, recursive functions need what is called a "base case". In other words, they need a way to stop.
In mathematics the factorial function is defined for natural numbers (i.e. integers >= 0).
0! is 1 and n! is n*((n-1)!)
As you can see factorial is defined in terms of factorial, and this makes it easy to implement recursively:
1
2
3
4
5
6
 
unsigned int factorial(unsigned int num) {
    if( num == 0 ) {
        return 1;
    }
    return num * factorial(num-1);
}

unsigned int is used because this function is based on natural numbers. Unsigned integers are always positive, because they cannot have a negative sign.

In your homework problem, you should try to work out the base case first. Let us know if you need help on that :)
Last edited on
enilc (5)
Thanks for the feedback shamieh.

I have implemented some of your suggestions. I have also modified my code after reading the link to the recursion tutorial. I know that I am still using if statements, but since they are contained within a recursive for loop, this is considered a recursive function. Is my understanding correct?

Again, thanks for the assistance.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 

#include <iostream>
#include <string>

using namespace std;

double vowels (string myString)
{

double vowelCount;
int count;
int strLength = myString.length();

vowelCount = 0;
count = 0;

for (count = 0; count < strLength; count++)
{
	if (myString[count] == 'A')
	{
		vowelCount = vowelCount + 1;
	}
	else if 	(myString[count] == 'E')
	{
		vowelCount = vowelCount + 1;
	}
	else if	(myString[count] == 'I')
	{
		vowelCount = vowelCount + 1;
	}
	else if (myString[count] == 'O')
	{
		vowelCount = vowelCount + 1;
	}
	else if 	(myString[count] == 'U')
	{
		vowelCount = vowelCount + 1;
	}
	else if 	(myString[count] == 'a')
	{
		vowelCount = vowelCount + 1;
	}
	else if 	(myString[count] == 'e')
	{
		vowelCount = vowelCount + 1;
	}
	else if 	(myString[count] == 'i')
	{
		vowelCount = vowelCount + 1;
	}
	else if 	(myString[count] == 'o')
	{
		vowelCount = vowelCount + 1;
	}
	else if 	(myString[count] == 'u')
	{
		vowelCount = vowelCount + 1;
	}
	else
		vowelCount = vowelCount;
}
return vowelCount;
}

int main()
{
double vowelTotal;
vowelTotal = vowels ("This is a test.");
cout << "Vowel Count: " << vowelTotal << endl;

return 0;
}
Last edited on
kevinkjt2000 (1063)
For loops are iterative, not recursive.
shamieh (161)
Though it is essentially the same thing, I think your teacher is wanting you to demonstrate a actual recursive loop with syntax, not just a loop that acts recursively. You're teacher wants you to write code with a recursive function. A recursive function is: a function that calls itself . I would figure out what your base case should be first as kevin suggested.
enilc (5)
Thanks kevinkjt2000. I thought so, but the article linked above was citing loops as recursive and used a for loop as an example.

I understand recursive versus iteration in mathematics. I do know that recursive formulas require a base case.

Let me think on this for a few minutes and see if I can write the base case.
Last edited on
shamieh (161)
Check this out, might help. (Also recursion is kind of hard to grasp when you first learn it, it was for me at least the first time I was taught it.)

https://www.youtube.com/watch?v=NvVYd08NUXI

EDIT: Posted wrong link, fixed now.
Last edited on
enilc (5)
Nevermind. I read too quickly. The language was confusing for me, but I see they transitioned from a for loop into recursion towards the end of the tutorial. I will try and work out my base case now. :)
kevinkjt2000 (1063)
I also wrote an example a few posts back about a recursive factorial. I think you might have missed it, because you posted an update of your code at the same time.

Recursive joke that someone told me:
someone wrote:
To understand recursion, you must understand recursion.
Smac89 (1727)
Hint:
1
2
3
4
 
std::string str = "my string"
if (str.find('s') != std::string::npos) {
    std::cout << "str contains 's'" << std::endl;
}
Duthomhas (13212)
That's a very useful hint, but it left out an important piece that OP may not see:

std::string str = "AEIOUaeiou";


ITERATIVE                                                   

A loop takes an index into the string:

for (int n = 0; n < s.length(); n++)


RECURSIVE                                                   

A recursive function must do the same thing.

int vowels( string s, int n )

Notice that the function returns an integer. (Returning a double seems to indicate that there can potentially be something like 3.7 vowels in a string.)

The next thing to notice is that n should always start at zero. You can make the function easier to call by doing that for the user:

int vowels( string s, int n = 0 )

Now they can say int vowelCount = vowels( "Hello world!" );

Inside the function, you must check to see if n is less than the number of items in the string.

if (n < s.length()

If it is not, you've reached the end of the string and there are no more vowels to find. Return zero.

Otherwise, you need to see if s[n] is a vowel.
If it is, the return value will be 1 + the number of vowels in the remaining string.
If not, the return value will be 0 + the number of vowels in the remaining string.

To get the number of vowels in the remaining string, simply call the function again, with an n equal to... n+1. Easy, right?

That's the recursion. Calling the current function.


RECURSIVE - PART II                                         

If you want, there's another way to go through the string. You can consider a string to be made up as:

    first character in the string, remaining characters in the string (if any)

So your function could look like:

int vowels( string s )

In order to find the number of vowels in the rest of the string, you'll need to call the function again, but not with the whole string. You'd need to call it with only the "remaining characters in the string". Use the substr() method for that:

return something + vowels( s.substr( 1 ) );

You should know what something is, right? (We just talked about it.)

What is the end condition? That is, when do we stop calling vowels() and just return zero?


Hope this helps.

[edit] Fixed typos.
Last edited on
shadder (813)
i may be out of topic but we could have really toned down the code for checking vowels using simple switch statements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
for (count = 0; count < strLength; count++)
{
swithc(myString[count])
   {
  case 'A' :
  case 'a':
  case 'E':
  case 'e':
  case 'I':

  ...

//you can predict the rest...

vowelCount++;
   }
}


a simple fall-through would make the code very short and sweet... :D
enilc (5)
I greatly appreciate everyone's help on here tonight. I have read the posts on this site for months, but I have been hesitant to create an account and post myself. I wish I had registered months sooner. I will be on again as I continue my journey learning C++. I was able to finally get the recursive function completed and working. Your hints and tutorials were immensely helpful in accomplishing this. Thank you again everyone. :)
Topic archived. No new replies allowed.