Count all contiguous substrings of string S where the first and last characters are the same. (USING RECURSION in C++)

#include <iostream>

using namespace std;

// Count how many times it starts and ends with same string

int go(string str, int i, int j, int n) {

    if(n == 1) {

        return 1;

    }

    

    if(n<=0) {

        return 0;

    }

    

    int res = go(str, i+1, j, n-1)+go(str, i, j-1, n-1)-go(str, i+1, j-1, n-2);

    

    if(str[i] == str[j]) {

        res++;

    }

    

    return res;

}

int main() {

    string S = "abcab";

    int size = S.length();

    

    cout << go(S, 0, size-1, size);

    

    

    return 0;

}

OUTPUT:

7