Your current recursive code is slightly incorrect, because the type of mid is int and not float. Once corrected, a recursive version of the iterative algorithm is:

final static float EPSILON = 0.00001;

static float sqrt(float n) {
    // Here, I use high = n for simplicity's sake.
    // In a real application, I'd special-case n = 0, …, 4
    // and start with high = n/2
    return recursiveSqrt(n, 0, n);
}

static float recursiveSqrt(float n, float low, float high) {
    float mid = (low + high) / 2;
    float midSquare = mid * mid;

    // This is the base case of the recursion
    // which corresponds to a loop condition.
    if (math.abs(midSquare - n) < EPSILON) return mid;

    // Anything that's not the base case recurses.
    // Here, we recurse either into the left or right half
    // of the currently processed interval
    if (midSquare > n) return recursiveSqrt(n, low, mid);
    else               return recursiveSqrt(n, mid, high);
}

Now, the Master Theorem is interested not in the specific implementation of the recursive function, but in three properties:

1. What is the running time at each step, excluding the recursion?
2. How often do we recurse per invocation?
3. How does the problem size shrink with each invocation?

Together, these define the parameters f(n), a, and b in the Master-Theorem equation

T(n) = a · T(n/b) + f(n)

that describes the complexity of some recursive functions. Note that the f(n) function is also a complexity expression. It describes the per-iteration overhead, which may depend on the problem size in each iteration.

The answer to the first question is that each invocation has constant running time (recursion excluded), because arithmetic operators, comparison operators, and Math.abs() take constant time. The only way to have non-constant time is to use loops or to invoke a function or method that has non-constant time – and we don’t do any of that. Therefore, f(n) = O(1).

Next, we have to determine how often we recurse. While the code contains two invocations of the recursive function, only one of them will be executed in any iteration. So a = 1.

Finally, we have to look at the problem size. The problem size of each iteration is not our parameter n. Instead, it is the range high - low. At each iteration, you halve this range by calculating the midpoint. Therefore, b = 2. It doesn’t matter where this range is and whether an iteration picks the lower or upper half. Only the size of the range matters. The initial size of the range is n.

Now we have determined all parameters necessary to apply the Master Theorem.

Our parameters do not match the first case where f(n) = O(nc) for some parameter c with c < logb(a): Here we have c = logb(a) = 0.

However, it immediately matches the second case where f(n) = Θ(nc · logk(a)) with k ≥ 0 and c = logb(a) (The character Θ that looks like a zero is actually the Greek letter uppercase Theta). Here, c = k = 0.

Then, the total complexity is T(n) = Θ(nc · logk + 1(n)) = Θ(log n).

Interpretation: This method for approximating a square root is essentially a binary search over the ordered sequence of all numbers between zero and n. This sequence is discrete, and all numbers in the sequence are 2·epsilon apart. At each iteration, we have lower and upper bounds delimiting a sublist which must contain the wanted list item. Because the sequence is ordered, we look at the item in the middle of the sub-sequence and then continue searching in the left or right sublist, depending on whether the middle item was larger or smaller than the wanted item. Consequently, this algorithm must have the same time complexity characteristics as a binary search.