This all comes down to the time it takes to compute
If these methods were implemented in the obvious way (
x.substring(1) builds up a new string by copying characters;
x.equals("") compares character-by-character until the first match), then
x.substring(1) would take $O(n)$ time and
x.equals("") would take $O(1)$ time (because it only looks at the first character of
x; if that is non-empty, it returns
So let's calculate the running time under the assumption that these methods are implemented in the obvious, naive way.
x.substring(1) returns a string of length $n-1$. Therefore, you recursively invoke
func() on a string of length $n-1$. Let $T(n)$ denote the running time of
func(x) when passed a string
x of length $n$. We obtain the recurrence relation
$$T(n) = T(n-1) + O(n).$$
(In other words, the recurrence you had is correct.) This recurrence solves to
$$T(n) = O(n^2);$$
see https://cs.stackexchange.com/a/2803/755 for details how. So, if those were the right assumptions about the running time of
equals(), the running time of your method would be $O(n^2)$.
However, it turns out that some versions of Java implement
substring() in a particularly clever way, with the result that
x.substring(1) takes only $O(1)$ time, not $O(n)$ time. In particular,
x.substring(1) doesn't make any copies of the string. Instead, it creates a new string object (call it
y) which has a pointer to
x and effectively says "hey, this string skips the first character of
x and starts at index 1".
Consequently, when you take into account this more sophisticated understanding of how
substring() works in some versions of Java, the recurrence becomes
$$T(n) = T(n-1) + O(1).$$
That solves to $T(n) = O(n)$. So, the total running time of your code is actually only $O(n)$, in those versions of Java, due to the clever way that Java implements the
See https://stackoverflow.com/q/4679746/781723 to learn more about the running time of
substring() and which of these analyses applies to you.