I recently did a Leetcode problem with recursion.
https://leetcode.com/problems/count-binary-substrings/

class Solution {
    public static int countBinarySubstrings(String s) {
        int res = 0;
        for(int i = 0; i < s.length()-1; i++) {

            if(s.charAt(i) != s.charAt(i+1)) 
                res += countValid(s, i, i+1);
        }
        return res;
    }

    public static int countValid(String s, int start, int end) {
        //base case
        if(start < 0 || end >= s.length()) 
            return 0;
        if(end-start == 1)
            return countValid(s, start-1, end+1) + 1;
        if(s.charAt(start+1) == s.charAt(start) && s.charAt(end-1) == s.charAt(end))
            return countValid(s, start-1, end+1) + 1;
        else
            return 0;
    }

}

The solution works but I have a hard time coming up with time complexity for recursive solutions.

Anytime the loop encounters s.charAt(i) != s.charAt(i+1), it makes recursive calls to expand until it reaches base case or the else part.

Since I'm traversing the entire string, the for loop is O(n). But how to determine the number of recursive calls that will be made since it will depend on the if condition.

As for the space complexity, the worst case occurs when s = "00...000011111...11". In this case, 01 occurs right in the middle so the recursive calls will keep on expanding until the start and end index are out of bounds. By then, the code will have made n/2 calls so the space complexity is O(N).

I'm stuck on the time complexity.