CODEWITHSUNDEEP
c++recursion
Richard Nguyen
Richard Nguyen

Reputation: 95

Is this the right way to use recursion?

Given strings s and t compute recursively, if t is contained in s return true.

Example: bool find("Names Richard", "Richard") == true;

I have written the code below, but I'm not sure if its the right way to use recursion in C++; I just learned recursion today in class.

#include <iostream>

using namespace std;

bool find(string s, string t)
{
    if (s.empty() || t.empty())
        return false;
    int find = static_cast<int>(s.find(t));
    if (find > 0)
        return true;
}

int main()
{
    bool b = find("Mississippi", "sip");
    string s;
    if (b == 1) s = "true";
    else 
        s = "false";
    cout << s;
}

If anyone find an error in my code, please tell me so I can fix it or where I can learn/read more about this topic. I need to get ready for a test on recursion on this Wednesday.

Upvotes: 0

Views: 416

Answers (4)

johnsyweb
johnsyweb

Reputation: 141998

The question has changed since I wrote my answer.

My comments are on the code that looked like this (and could recurse)...

#include <iostream>

using namespace std;

bool find(string s, string t)
{
    if (s.empty() || t.empty())
        return false;
    string start = s.substr(0, 2);
    if (start == t && find(s.substr(3), t));
        return true;
}

int main()
{
    bool b = find("Mississippi", "sip");
    string s;
    if (b == 1) s = "true";
    else 
        s = "false";
    cout << s;
}

Watch out for this:

if (start == t && find(s.substr(3), t));
    return true;

This does not do what you think it does.

The ; at the end of the if-statement leaves an empty body. Your find() function will return true regardless of the outcome of that test.

I recommend you turn up the warning levels on your compiler to catch this kind of issue before you have to debug it.

As an aside, I find using braces around every code-block, even one-line blocks, helps me avoid this kind of mistake.

There are other errors in your code, too. Removing the magic numbers 2 and 3 from find() will encourage you to think about what they represent and point you on the right path.

How would you expect start == t && find(s.substr(3), t) to work? If you can express an algorithm in plain English (or your native tongue), you have a much higher chance of being able to express it in C++.

Additionally, I recommend adding test cases that should return false (such as find("satsuma", "onion")) to ensure that your code works as well as calls that should return true.

The last piece of advice is stylistic, laying your code out like this will make the boolean expression that you are testing more obvious without resorting to a temporary and comparing to 1:

int main()
{
    std::string s;
    if (find("Mississippi", "sip"))
    {
        s = "true";
    }
    else
    {
        s = "false";
    }
    std::cout << s << std::endl;
}

Good luck with your class!

Upvotes: 4

bitmask
bitmask

Reputation: 34714

You are not using recursion. Using std::string::find in your function feels like cheating (this will most likely not earn points).

The only reasonable interpretation of the task is: Check if t is an infix of s without using loops or string functions.

Let's look at the trivial case: Epsilon (the empty word) is an infix of ever word, so if t.empty() holds, you must return true. Otherwise you have two choices to make:

  1. t might be a prefix of s which is simple to check using recursion; simply check if the first character of t equals the first character of s and call isPrefix with the remainder of the strings. If this returns true, you return true.
  2. Otherwise you pop the first character of s (and not of t) and proceed recursively (calling find this time).

If you follow this recipe (which btw. is easier to implement with char const* than with std::string if you ask me) you get a recursive function that only uses conditionals and no library support.

Note: this is not at all the most efficient implementation, but you didn't ask for efficiency but for a recursive function.

Upvotes: 0

Gordon Gustafson
Gordon Gustafson

Reputation: 41259

Your recursive function needs 2 things:

  1. Definite conditions of failure and success (may be more than 1)
  2. a call of itself to process a simpler version of the problem (getting closer to the answer).

Here's a quick analysis:

bool find(string s, string t)
{
    if (s.empty() || t.empty())  //definite condition of failure. Good
        return false;
    string start = s.substr(0, 2);
    if (start == t && find(s.substr(3), t)); //mixed up definition of success and recursive call
        return true;
}

Try this instead:

bool find(string s, string t)
{
    if (s.empty() || t.empty())  //definite condition of failure. Done!
        return false;
    string start = s.substr(0, 2); 
    if (start == t)  //definite condition of success. Done!
        return true;
    else            
        return find(s.substr(3), t) //simply the problem and return whatever it finds
}

Upvotes: 2

Jim
Jim

Reputation: 73966

You're on the right lines - so long as the function calls itself you can say that it's recursive - but even the most simple testing should tell you that your code doesn't work correctly. Change "sip" to "sipx", for example, and it still outputs true. Have you compiled and run this program? Have you tested it with various different inputs?

Upvotes: 0

Related Questions