Are there problems for which divide-and-conquer / recursion is provably useless? When we try to construct an algorithm for a new problem, divide-and-conquer (using recursion) is one of the first approaches that we try. But in some cases, this approach seems fruitless as the problem becomes much more complicated as its input grows.

My question is: are there problems for which we can prove that a divide-and-conquer approach cannot help to solve? In the following lines I try to make this more formal.

Let $P(n)$ be a certain problem whose input has size $n$ (e.g. a problem that accepts an input an array of $n$ numbers). Suppose we have a recursive algorithm for solving $P(n)$.    The recursive runtime of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k&lt;n$ in constant time. For example:


The recursive runtime of binary search is $O(1)$, since it uses only a comparison and two recursive calls.
The maximum element in an array can be found in recursive time $O(1)$.
The recursive runtime of merge sort is $O(n)$, because of the merging step.


The recursive time is usually smaller than the actual runtime, which reflects the fact that the recursive algorithm is simpler than a straightforward non-recursive solution to the same problem.

Now my question is:

Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime asymptotically less than $f(n)$?

Some specific variants of this question are:


Is there a problem in $P$ which has no algorithm with recursive runtime $O(1)$? (Maybe sorting?)
Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?


EDIT: contrary to my guess, sorting has an algorithm with recursive runtime $O(1)$. So it is still open, whether there a problem in $P$ which has no algorithm with recursive runtime $O(1)$.
Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?


Yes.  Note that if a tally language has “recursive algorithm” with polynomial “recursive runtime,” then it is in P.  There is a tally language in E∖P by a standard diagonalization argument.


  Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime $o(f(n))$?


It may depend on the computational model, but I doubt this is known, given that the time hierarchy theorem for two-tape Turing machines is not powerful enough to distinguish, say, O(n2) time and o(n2) time even without giving the latter the constant-time access to the answers on smaller instances.



Random comments on your questions in this post:


I do not think that these questions are related to the usefulness of recursive programs, despite what the title of the post and your choice of terminology suggest.  As BVMR wrote in an answer, recursions and iterations are equivalent in a certain sense.  Instead, I think that the questions have a connection to the usefulness of the divide-and-conquer approach.
In complexity theory, a related notion to your notion of “recursive algorithms” with their “recursive runtime” is called “length-decreasing self-reductions” with their time complexity.
Some part of your questions (definitely the part referring to sublinear-time algorithms) depend on the choice of computational model.