Substring recursive algorithm not working

Question

I'm a programming student in my first C++ class, and recently we were encouraged to write a simple recursive function to find the first occurrence of a substring in a given string. If found, it returns the index. If the substring is not found, the index_of() function should return -1. We are encouraged to use a helper function that takes the index as one of its parameters, and this is what I've tried.

For example:

int index_of("Mississippi", "sip"); // this would return a 6

This is supposed to be a simple exercise to help us understand recursion and won't be turned in. My professor stated that our actual assignment with recursion will be much more involved, which is why I really want to understand this simple use of recursion.

I've done this successfully using C-style strings and pointers, but not with C++ std::string objects. What am I doing wrong in my program? My professor stated we should easily be able to write this in 5 mins, but I've been struggling with it for two hours. Here's what I've done so far:

int index_of(string s, string t)
{
    int index = 0;

    if (s[index] == NULL)
        return -1;
    else if (starts_with(s, t, ++index))
    {
        return index;
    }
    else 
        return index;
}

bool starts_with(string s, string t, int index)
{
    if (t[index] == NULL)
        return true;
    if ( s[index] == NULL || t[0] != s[index])
        return false;
    return starts_with(s, t, ++index);
}

As written, this function always returns an index of 1.

Answer 1

Your code boils down to this

int index_of(string s, string t)
{
    int index = 0;

    //if (s[index] == NULL)
    //    return -1;
    ++index // from this: else if (starts_with(s, t, ++index))
    //{
    //    return index;
   // }
   //else 
        return index;
}

so, yes, it always returns 1

index continues to increment inside the recursive starts_with function, but the changed values never make it back out to be your return value.

Answer 2

You are not updating the index variable in the index_of() function. When you pass it to starts_with() it makes a copy on the stack. You need to return the updated value somehow - ether take it by reference/pointer or return it instead of bool.

Answer 3

I don't think 5 minutes was at all a reasonable estimate for an intro class student. To help you get even help you understand the issue, I've written what I think is the final answer...

#include <string>
#include <iostream>
using namespace std;

int starts_with(string s, string sub, unsigned int i) {
  if (i >= s.length())
    return -1;
  if (s.compare(i, sub.length(), sub) == 0)
    return i;
  return starts_with(s, sub, i + 1);
}
int index_of(string s, string sub) { return starts_with(s, sub, 0U); }
int main(void) { cout << index_of("Mississippi", "sip") << "\n"; }

Answer 4

(note - edited for simplicity)

Not sure if this'll help as I'm not sure to what extent recursion was explained to you by your teacher, but here goes...

This is how you need to think of it - A recursive function contains two main components:

1) a Base Case and

2) a Recursive Case

The key is that on each call, you are determining which of the two cases is true for this run of the function (based on the input parameter(s)).

The base case is where the function is not called again, and the recursive case always calls the function, and is usually more complicated in its logic than the base case.

---

So I'd suggest starting over. Think about what the input should be such that on a function call with that input the function does not call itself ---> that's your base case.

If on a function call it isn't the base case, it's the recursive case. So your function needs to look like this:

function index_of(params...){
    if base case
        do something simple and return
    else
        do something and call index_of again
}

Hint: In your function, there is no recursive case.