What is time complexity of recursive solution?

Let's first suppose that
 the length of s is n
 length of p is m
The typical recursive solution will be as follows. One thing should be pointed out the searching tree of the recursion (each node will have one child or two at most):
no matter what is to happen the index of either s or p will be incremented in the next recursive function so the worst case of the depth will be n+m
but as we can clearly spot it that only when the
*(p+1)=='*'
there will be two subtraversals and only when theisMatch(s, p+2)
is false the second part will be checked  since they are connected byor
; so the worst traversing case will be O(2^n).As for redundant checking, the simplest case is when there are several
*
which will definitely result in some small subsearchingtrees overlapping since each traversing branch will check all of its branch until the end.
bool isMatch(char *s, char* p) { if(*p == '\0') return *s=='\0'; if(*(p+1) == '*') return isMatch(s, p+2)  //match zero letter in s; ((*s==*p  '.'==*p) && isMatch(++s, p)); //match one or more; else return *s!='\0' && (*s==*p  '.'==*p) && isMatch(++s, ++p); }
