Recursion and strings

[xanthian23]

Hi, I have an assignment I am working on that uses recursion. I'm still having a little trouble understanding recursion, or at least how it all works, but I think I'm starting to grasp it, even though I'm not all that sure why anything works.

My assignment has two parts, but for the moment, I just need a little help with the first part. Here's what I have to do:

Write a recursive function that will return the position of the first occurence of a character within a C String

This is what I have so far...

#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
int test(string s, char x);

int main ()
{
  test("lets test for the letter s", "s" );
}

int test(string s, char x)
{
	if(s.length() == 0)
		return 0;
	else if (s[0] == x)
		return 1 + test(s.substr(1, s.length()), x);
	else
		return test(s.substr(1, s.length()), x);
}

So i think this should work, but I'm a little confused as to how to get the function to test anything. I'm pretty sure I have the string part done correctly in my function call in main, but I can't get the char to accept a value. The way I understand it, i should enter the text I want to scan, and then the character I want to look for. Can anyone tell me what I am doing wrong, or even I'm even close with the recursive function?

[Stewbond]

One way to use recursion is to replace simple looping with it. Looking at your code, I see a few issues:

1. You are using std::string (C++ strings not C strings). If I were to implement this with std::string I would do this:

int test (string s, char x)
{
    return s.find(x);
}

2. You are passing "s" as a char. You should pass 's' ("s" is a pointer to a character array of 2 (s \0)

I would do it this way:

int test(char* str, char x, int pos = 0)
{
    if (str[pos] == '\0') return -1; // -1 indicates "not found"
    if (str[pos] ==  x  ) return pos;
    return test(str, x, pos+1);
}

though I suppose you could also do it this way (though these is no way to check for npos):

int test(char* str, char x)
{
    if (*str == '\0') return 0;
    if (*str ==  x  ) return 0;
    return 1 + test(str+1, x);
}

[xanthian23]

Yeah, I caught the ' ' thing already, stupid me.

As for the code, I switched to this:

int test(string s, char x)
{
	if(s.length() == 0)
	{
		cout << "There is no instance of the letter you are looking for in this string " << endl;
		exit(0);
	}
	else if (s[0] == x)
		return 0;
	else
		return 1 + test(s.substr(1, s.length() -1), x);
}

Not much different, but it takes into account the chance of there being no lotter, and returns a zero if the letter is the first in the string.

So your version would take three arguments instead of two, one of which being the zero location indicator. You have nothing found covered as well. My question is how does that last one work? I get that its the recursive part, I just don't understand how it works.

[Stewbond]

int test(char* str, char x, int pos = 0)
{
    if (str[pos] == '\0') return -1; // -1 indicates "not found"
    if (str[pos] ==  x  ) return pos;
    return test(str, x, pos+1);
}

is equivalent to:

int test(char* str, char x, int pos = 0)
{
    while(true)
    {
        if (str[pos] == '\0') return -1;
        if (str[pos] ==  x  ) return pos;
        pos++;
    }
}

It just increments pos and repeats. Note the int pos = 0 in the declaration makes the parameter optional. If not defined, it will start at 0 (representing the beginning). If it is defined, it will start at the position that you have defined.

The second one:

int test(char* str, char x)
{
    if (*str == '\0') return 0;
    if (*str ==  x  ) return 0;
    return 1 + test(str+1, x);
}

would be equivalent to:

int test(char* str, char x)
{
    int pos = 0;
    while(true)
    {
        if (*str == '\0') return pos;
        if (*str ==  x  ) return pos;
        pos++; 
        str++;
    }
}

It increments the pointer itself so that it points at the next element. Then returns the number of times it was incremented. It uses pointer arithmetic which is confusing and generally not recommended if there are other solutions. I provided it so that you could see a version which only took 2 arguments.

[Stewbond]

But really, if you are going to use std::string and not C strings, you should really look at:
http://cplusplus.com/reference/string/string/find/

If you can use methods like .length() or .substr(), then there should be nothing stopping you from using .find() because that function is in the same class as .length() or .substr(). This makes me thing that you shouldn't be using std::string for your assignment (though I highly recommend using it over char* for any practical application)

[vlad from moscow]

There is such C standard function strchr. It returns pointer to the target character in the source character array or 0 if the character was not found. So your recursive function I think should have the same logic

char * MyStrChr( const char *s, char c )
{
	if ( *s == '\0' ) return 0;
	return ( *s == c ? ( char * )s : MyStrChr( ++s, c ) );
}

If the character will be found to get the index is simple. It is equal to MyStrChr( s, c ) - s;

[xanthian23]

Here's a good one, it's not a part of my assignment, but I'm curious, how would I go about scanning the entire string for every instance of a letter

[derekroolz]

if (*str == '\0') return 0;
if (*str ==  x  ) return 0;
return 1 + test(str+1, x);

This code is good, but it is flawed. When it is given a string that is checked with a char that is not in the string, it returns the lengths of string rather than -1. Having -1 return in this case is desired because it tells the user that the char did not appear anywhere in the index, since the index needs to be >= 0.

In order to fix this, the creation of a third argument is needed that we will call count of type int. This is the code I created to overcome this issue.

main()
{
cout << "The location of your letter was found at " 
        << catcher(strInput, charInput, 1) << endl;
// strInput and charInput is user defined in main. 
//Also, 1 is passed for count since that is always going to be the first function
//call of catcher... Limits functionality slightly, but this can be overcome by 
//keeping count as a static int.
}
int catcher(char *strTest, char firstOccur, int count)
{
	if(*strTest == '\0') return -count;//Bad
	if(*strTest == firstOccur) return 0;
	return 1 + catcher(strTest + 1, firstOccur, count + 1);
}

[xanthian23]

Ok, let me try and understand this, (assuming I can).

Your overloading the int with a pointer to a string, a char input, and another int for counting.

First, if the pointer to the string hits the zero, or the end of the string you return a negative count? or is that if you hit a string without the character your looking for?

Second, if the pointer to the string matches the defined char were looking for, you return a zero? I'm still a bit confused how returning a zero works in showing a numerical location above zero. I'm guessing that its the recursive return on the function itself that takes that info and actually pops out the location.

I'm a little lost on how the final return works for the actual counting. you have 1 plus wht your function returns, which is popping out 1 plus the pointer to the string, and I don't get where the char contributes in the final call, and then you have a count plus one.

Yeah, I don't really understand this. Doesn't passing 1 for count make it skip the char at spot zero? I probably sound like a moron right now, but I don't get it yet. I'm going to play around with this and see if I can understand it better, thanks for the post though!

[Stewbond]

derekroolz wrote:

This code is good, but it is flawed.

That's why I recommended the first option. The problem with that kind of recursion where you don't track the progress, is that you lose the ability to report how many recursions it took. Of course, you could do what vlad suggested and put some logic in the calling code, but the whole purpose of a function is to prevent the user from doing to much on their end.

You came up with a solution, but I think a better solution is to avoid pointer arithmetic all together:

int test(char* str, char x, int pos = 0)
{
    if (str[pos] == '\0') return -1; // -1 indicates "not found"
    if (str[pos] ==  x  ) return pos;
    return test(str, x, pos+1);
}

[xanthian23]

Yeah, my code is based off of something I learned in java a few year ago, but it uses the charAt() in lieu of my solution to the charAt, which was a string[]. I'm having trouble wrapping my head around using a pointer to a string in the overload, and how it works in the recursion.

[derekroolz]

"First, if the pointer to the string hits the zero, or the end of the string you return a negative count? or is that if you hit a string without the character your looking for?

Second, if the pointer to the string matches the defined char were looking for, you return a zero? I'm still a bit confused how returning a zero works in showing a numerical location above zero. I'm guessing that its the recursive return on the function itself that takes that info and actually pops out the location.

I'm a little lost on how the final return works for the actual counting. you have 1 plus wht your function returns, which is popping out 1 plus the pointer to the string, and I don't get where the char contributes in the final call, and then you have a count plus one.

Yeah, I don't really understand this. Doesn't passing 1 for count make it skip the char at spot zero? I probably sound like a moron right now, but I don't get it yet. I'm going to play around with this and see if I can understand it better, thanks for the post though!"



I feel like a mathematician that is troubled in the sense of figuring out how to explain his work. Albert Einstein quote?

“If you can't explain it to a six year old, you don't understand it yourself.”
― Albert Einstein

Alright, so. Answering your first paragraph. If it hits the 0, I assume you mean '\0' which is the NULL character (indicating the end of the string) rather than a value of 0, I believe you stated that in the second part of the sentence. But, just to be clear, it is going until the NULL character is reached. Essentially, I will write out my three lines in pseudo-code to help make sense of it all.

	if(*strTest == '\0') return -count;//Bad
	if(*strTest == firstOccur) return 0;
	return 1 + catcher(strTest + 1, firstOccur, count + 1);

Line 1: if pointer to the string "strTest" is equivalent to NULL, return -count.

Why does this work and return a value of -1? We pass into my function catcher from main; strTest, a char to check and 1. We pass 1 because that is considered it's first function call, hence the literal value of 1 for count (count keeps track of function calls. From there, 1 gets stored into the address of int count inside the function call. Then, all three arguments are passed to the function catcher.

The function catcher opens up and checks the first line. Is the pointer to the string equivalent to NULL, no. I can't think of anything you could input into the console window that would allow this first condition to be immediately true given that an actually pointer to a string is given, even so, count has a value of 1 and then is multiplied by a negative and would return -1.

Line 2: if pointer to the string "strTest" is equivalent to char being checked at first function call (index 0) return 0.

Line 3: return a value of 1 added to the value of whatever the next call of catcher returns. THE MOST IMPORTANT NOTE HERE IS THAT THIS IS CONSIDERED AN INCOMPLETE FUNCTION CALL!!!!! it is not returned, yet. The argument "strTest" is incremented by 1 to increase the index to the next value. The char to check is left as is since we need only to be checking this char for the first time it appears. We then add a value of 1 to position because this is the next(right now second) time the function has been called.

It then begins the function again, a recursion as it is called. Now we can begin to see how the logic will return the numbers correctly.

**Note, to help you understand the first call we had line 1, 2, 3. for this recursion we will call them line 1a, 2a, 3a, to indicate that it has been recurred once. (b recurred twice, c recurred three times, etc.)**

so, count on it's second call has a value of 2.

line 1a: if true, return -count for this a value (-2). We then see that this is a complete function and is returned to our incomplete function call with a value of -2. Hence, line 3 then has the value of -2 is passed back up to it and 1 is added to it.

line 3: return 1 + catcher(strTest + 1, firstOccur, count + 1);

but what if line 1a is false? We go to line 2a.

Line 2a: if the char being checked is found on the next index of strTest (now index 1) return 0; We then complete this function call by returning 0 and adding 1 to it on line 3.

but what if line 1a, and 2a, were false? We go to line 3a.

add 1 to the pointer of the strTest index,(index 2) pass the char to check and add 1 to count (3, this is the third function call) This then creates another INCOMPLETE function call that will have a value of 1 added to it once completed. Ahh, do we see now? If not, no worries. Let's repeat the process just to be sure.

line 1b: if true return -count (-3) this completes this function call and -3 is brought up to line 3a which is incremented by 1, giving it a value of -2, this completes this function call and -2 is brought up to line 3. Which is incremented by 1 finally completing the initial function call returning a value of -1.

BUT WHAT IF LINE 1b is false?! Then we move to line 2b.

line 2b: if char being checked is found on the next index of strTest (now index 2) return 0; This completes this function call and returns 0, 0 is passed up to line 3a, which is incremented by 1 which in turn completes that function call returning and returns with a value of 1, then finally being passed up to line 3 and you guessed it, incremented by 1 completing the initial function call with a return value of 2.

It should now be apparent what is happening here. Thus, we conclude,

•line 1 is being used to see if the end of string has been reached.
•line 2 is being used to return the value of the position of the index in which the char occurred, if any.
•line 3 is being used to create more functions calls if;
line 1 is not true (the string hasn't been fully searched) and if
line 2 is not true (the char has not been ran into)
However, if line 1 is true on the next function call (end of string and thus cannot continue to line 2 or 3 of that recursion) created by line 3, return the amount of times the function has been called in form of negative numbers and it will be incremented by 1 times the number of recursions that occurred (YOUR FIRST FUNCTION CALL IS NOT A RECURSION, THUS IT WILL COMPLETE WITH -1, always)

or if line 2 is true on the next function call because the end of the string has not been reached (our character has been found) then return 0, since we start at index 0, and multiply by 1 times the number of recursions that occurred.


This completes my lecture on recursions for this specific example. Hope you enjoyed.