As a matter of c/c++ efficiency, passing a string as a parameter is costly. It's more useful to store the string globally (because it doesn't change) and use an int as your index in the string as your parameter for your recursion .
As @daft_wullie alluded to, let's take a look at what you know so far.
Your recursion essentially walks from left to right through the string. When it reaches the end of the string (length one or two) it returns a result and resumes the recursion. Will the answer for those final steps (length 1 and 2) ever change, or will they always be the same? Think about how many times you will call that final step. Now examine the other lengths, will their results always be the same? Now you're looking at a more straightforward problem.