Why is the time complexity of this algorithm exponential?

During an interview, I was asked the time complexity of the following algorithm:

static bool SetContainsString(string searchString, HashSet<string> setOfStrings)
{
    for (int i = 0; i < searchString.Length; i++)
    {
        var segment = searchString.Substring(0, i + 1);

        if (setOfStrings.Contains(segment))
        {
            var remainingSegment = searchString.Substring(segment.Length);

            if (remainingSegment == "") return true;
            return SetContainsString(remainingSegment, setOfStrings);
        }
    }

    return false;
}

I answered "linear" because it appears to me to loop only through the length of searchString. Yes, it is recursive, but the recursive call is only on the portion of the string that has not yet been iterated over, so the end result number of iterations is the length of the string.

I was told by my interviewer that the time complexity in the worst case is exponential.

Can anyone help me clarify this? If I am wrong, I need to understand why.