The recursion depth is because you halve the state range each time. At each depth, the search ranges across all calls are nearly disjoint. When you find , the left child gets range and the right child gets . These don't overlap except at .
So all calls at the same depth search a total of values. With depths, total work is . For layered DP with layers, you run D&C once per layer: total.