<p>Any question which has recursive answer has iterative answer and vice versa.</p>

<p>Any recursive algorithm can be rewritten in iterative way and vice versa.</p>

<p>Hence, your question doesn't stand good.</p>

CC BY-SA 3.0
2014-10-17T14:19:59.910Z
The complexity of an algorithm, as I defined it in the question, generally does not remain the same when it is converted from iterative to recursive. For example, the maximum of n elements can be found by an iterative algorithm with O(n) operations, but it can also be found by a recursive algorithm with O(1) operations (one of which is a recursive call). Although finally the runtime of both algorithms is the same, the recursive algorithm is simpler to program because it has less operations.
Erel Segal-Halevi
CC BY-SA 3.0
2014-10-17T13:14:38.803Z
2014-10-17T13:14:38.803Z
BVMR
<p>I am not sure if I correctly understand your notion of "recursive complexity". </p>

<p>Lets (reasonably) Assume a programming language that contains a schema for primitive recursion i.e. in which one can define functions $f$ from</p>

<p>$$
f(0,\vec x) = c(\vec x)\\
f(n+1,\vec x) = g(f(n,\vec x),n,\vec x) 
$$</p>

<p>where $c$ and $g$ are previously defined functions. Further let us assume that the basic functions (constants, projections, successor) have $\mathcal{O}(1)$ "recursive complexity" If I understand your definition correctly, then all primitive recursive functions (and thus problems/relations) have $\mathcal{O}(1)$ "recursive runtime". This, I think, can be seen by induction on the build up of recursive functions.</p>

<p>If all my assumptions are met, then the example you are looking for cannot be primitive recursive.</p>

CC BY-SA 3.0
2016-01-11T16:20:59.837Z
please elaborate on the downvotes
D.F.F
CC BY-SA 3.0
2016-01-12T09:08:43.323Z
From the question, "The recursive runtime of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k<n$ in constant time." . This definition of runtime gives naturally a rise to a complexity measure. This is a fancy way of saying that we do not care about the cost of lower size recursions, but only of the current step. So in your notation, we ask what is the complexity of comuting $g(f(n,x),n,x)$ given an oracle for $f(n,x)$ that has constant runtime.

I didn't downvote you, but this is a year-old answered question and you also misinterpreted a given definition.
chazisop
CC BY-SA 3.0
2016-01-12T11:15:41.670Z
thanks for your comment. I think I understood the definition. Since $g$ is a prim. rek. function, by induction hypothesis it has runtime $\mathcal{O}(1)$ since $f(n,x)$ is given by the oracle in constant time, evaluating the whole expression takes $\mathcal{O}(1\circ 1)=\mathcal{O}(1)$.
D.F.F
CC BY-SA 3.0
2016-01-14T10:30:43.100Z
You have to use the full complexity for $g$, not its recursive complexity. That's not $O(1)$.
Emil Jeřábek
CC BY-SA 3.0
2016-01-14T10:40:09.063Z
ahh, ok... now everything makes sense... thanks for the clarification... I was probably confused by the fact that recursive complexity is not invoked recursively^^ (which is not very celar from the definition imo)
D.F.F
CC BY-SA 3.0
2016-01-11T14:30:48.440Z
2016-01-11T14:30:48.440Z
D.F.F
<blockquote>
  <p>Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?</p>
</blockquote>

<p>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.</p>

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

<p>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(<i>n</i><sup>2</sup>) time and o(<i>n</i><sup>2</sup>) time even without giving the latter the constant-time access to the answers on smaller instances.</p>

<hr>

<p>Random comments on your questions in this post:</p>

<ul>
<li>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.</li>
<li>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.</li>
<li>Some part of your questions (definitely the part referring to sublinear-time algorithms) depend on the choice of computational model.</li>
</ul>

CC BY-SA 3.0
2014-10-18T20:18:49.240Z
Regarding your first answer: let me try to expand it to see if I understand correctly. Assume that a certain tally language has an algorithm with polynomial "recursive runtime". A polynomial algorithm for this language can be constructed using dynamic programming. The answer for $n=0$ can be found in polynomial time since no recursive calls are required. The answer for $n=1$ can then be found in polynomial time using the answer for $n=0$. Then answer for $n=2$ can be found in polynomial time using the answers for $n=1$ and $n=0$, etc.  Is this correct?
Erel Segal-Halevi
CC BY-SA 3.0
2014-10-18T20:33:59.077Z
Yes, although it is better to avoid asymptotic notions such as “polynomial time” when you talk about a particular value of n; for example, it does not make sense to say “the algorithm runs in polynomial time when n=0.”  If a tally language has a “recursive algorithm” with polynomial “recursive runtime” p(n), then we can compute the answer for n without the oracle by computing the answers for 0, 1, 2, …, n, and this takes time $O(\sum_{i=0}^n p(i))$, which is polynomial in n.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-20T07:30:33.843Z
Thanks. I agree with your comment about divide-and-conquer and I edited the question accordingly.
Erel Segal-Halevi
CC BY-SA 3.0
2014-10-18T09:02:46.813Z
2014-10-20T10:27:23.470Z
2014-10-20T10:27:23.470Z
Tsuyoshi Ito
<p>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.</p>

<p>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.</p>

<p>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 <em>recursive runtime</em> of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k&lt;n$ in constant time. For example:</p>

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

<p>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.</p>

<p>Now my question is:</p>

<p><strong>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)$?</strong></p>

<p>Some specific variants of this question are:</p>

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

<p>EDIT: contrary to my guess, <a href="https://cs.stackexchange.com/a/32122/1342">sorting has an algorithm with recursive runtime $O(1)$</a>. So it is still open, whether there a problem in $P$ which has no algorithm with recursive runtime $O(1)$.</p>

CC BY-SA 3.0
2014-10-17T15:22:59.600Z
Maybe proving a kernelization lower bound would do the trick http://en.wikipedia.org/wiki/Kernelization
Tyson Williams
CC BY-SA 3.0
2014-10-17T15:53:30.540Z
The output size is a lower bound on the running time.
Thus any problem with output size matching its complexity has this property.
Chao Xu
CC BY-SA 3.0
2014-10-18T02:31:51.633Z
@Chao Xu: Why doesn’t your argument apply to the input size?  I think that the argument depends on which cost model (and computational model) we consider.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-18T05:32:58.240Z
This is the opposite of what you're looking for, but given those oracles your model can solve subset sum - a known NP-Complete problem - in linear time, thus assuming P!=NP it's much more powerful than iterative functions in this case.

The function would simply check if the current set adds to 0, then if not it calls itself on the n subsets of size n-1. The runtime itself is n! however, which is worse than brute force, so I'm not really sure how much value this model provides, but it's still an interesting question.
Phylliida
CC BY-SA 3.0
2014-10-18T05:59:11.117Z
Also, for any problem couldn't you just write a "recursive" algorithm that doesn't bother to call itself and uses the iterative algorithm instead? It can also spam some calls to oracles in there if it's required and just discard the results, since calls to them is $\mathcal{O}(1)$. Thus I think you'd need some sort of additional formalism that describes that you're required to meaningfully use recursion. Specifically iteration algorithms can't be a subset of your recursive ones otherwise it's impossible for iterative ones to do what recursive ones can't, your other questions still work though.
Phylliida
CC BY-SA 3.0
2014-10-18T14:56:31.977Z
it is known roughly since the invention of lambda calculus that there is not really any discriminating way to define "recursion" that is not also Turing complete. in other words there is no strict technical differentiation of a recursive from a nonrecursive program in CS, both are always convertible to each other no matter how each is (sensibly) defined (using the more informal sense of "recursion" as "calls itself" not the technical meaning). so this is (reduces to) really more of a general question on lower bounds for algorithms which are still mostly (T)CS fields massive "dark matter"...
vzn
CC BY-SA 3.0
2014-10-18T16:35:07.630Z
@DaniPhye of course you can add useless recursive calls, but this will not improve the runtime... usually, using recursive oracles can improve the runtime, as in the 3 examples I mentioned in the question. My question is, whether there are problems for which recursive oracles *cannot* improve the runtime.
Erel Segal-Halevi
CC BY-SA 3.0
2014-10-18T23:38:25.263Z
@Erel Sorry you're right, I missed the little o notation. We can delete these three comments if you'd like.
Phylliida
CC BY-SA 3.0
2014-10-20T13:25:16.880Z
Your recent edit ("recursive" -> "divide-and-conquer") is a pretty big change to the question. I would just post a separate question instead. We can probably say things about divide-and-conquer by looking for instance at the depths of circuits.
usul
<cc.complexity-theory><recursion>
Are there problems for which divide-and-conquer / recursion is provably useless?
Erel Segal-Halevi
# Are there problems for which divide-and-conquer / recursion is provably useless?

(Asked by: username_0 on 2014-10-17)

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

* 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)$](https://cs.stackexchange.com/a/32122/1342). So it is still open, whether there a problem in $P$ which has no algorithm with recursive runtime $O(1)$.

**Tags:** cc.complexity-theory, recursion
> **Comments:**
> **username_1**: Maybe proving a kernelization lower bound would do the trick http://en.wikipedia.org/wiki/Kernelization  
> **username_2**: The output size is a lower bound on the running time. Thus any problem with output size matching its complexity has this property.  
> **username_3**: @Chao Xu: Why doesn’t your argument apply to the input size?  I think that the argument depends on which cost model (and computational model) we consider.  
> **username_4**: This is the opposite of what you're looking for, but given those oracles your model can solve subset sum - a known NP-Complete problem - in linear time, thus assuming P!=NP it's much more powerful than iterative functions in this case.  The function would simply check if the current set adds to 0, then if not it calls itself on the n subsets of size n-1. The runtime itself is n! however, which is worse than brute force, so I'm not really sure how much value this model provides, but it's still an interesting question.  
> **username_4**: Also, for any problem couldn't you just write a "recursive" algorithm that doesn't bother to call itself and uses the iterative algorithm instead? It can also spam some calls to oracles in there if it's required and just discard the results, since calls to them is $\mathcal{O}(1)$. Thus I think you'd need some sort of additional formalism that describes that you're required to meaningfully use recursion. Specifically iteration algorithms can't be a subset of your recursive ones otherwise it's impossible for iterative ones to do what recursive ones can't, your other questions still work though.  
> **username_5**: it is known roughly since the invention of lambda calculus that there is not really any discriminating way to define "recursion" that is not also Turing complete. in other words there is no strict technical differentiation of a recursive from a nonrecursive program in CS, both are always convertible to each other no matter how each is (sensibly) defined (using the more informal sense of "recursion" as "calls itself" not the technical meaning). so this is (reduces to) really more of a general question on lower bounds for algorithms which are still mostly (T)CS fields massive "dark matter"...  
> **username_0**: @DaniPhye of course you can add useless recursive calls, but this will not improve the runtime... usually, using recursive oracles can improve the runtime, as in the 3 examples I mentioned in the question. My question is, whether there are problems for which recursive oracles *cannot* improve the runtime.  
> **username_4**: @Erel Sorry you're right, I missed the little o notation. We can delete these three comments if you'd like.  
> **username_6**: Your recent edit ("recursive" -> "divide-and-conquer") is a pretty big change to the question. I would just post a separate question instead. We can probably say things about divide-and-conquer by looking for instance at the depths of circuits.  

---

## 3 answers

### Answer by username_3 on 2014-10-18. Score: 8 | Accepted answer

> 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(*n*2) time and o(*n*2) 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.

> **Comments:**
> **username_0**: Regarding your first answer: let me try to expand it to see if I understand correctly. Assume that a certain tally language has an algorithm with polynomial "recursive runtime". A polynomial algorithm for this language can be constructed using dynamic programming. The answer for $n=0$ can be found in polynomial time since no recursive calls are required. The answer for $n=1$ can then be found in polynomial time using the answer for $n=0$. Then answer for $n=2$ can be found in polynomial time using the answers for $n=1$ and $n=0$, etc.  Is this correct?  
> **username_3**: Yes, although it is better to avoid asymptotic notions such as “polynomial time” when you talk about a particular value of n; for example, it does not make sense to say “the algorithm runs in polynomial time when n=0.”  If a tally language has a “recursive algorithm” with polynomial “recursive runtime” p(n), then we can compute the answer for n without the oracle by computing the answers for 0, 1, 2, …, n, and this takes time $O(\sum_{i=0}^n p(i))$, which is polynomial in n.  
> **username_0**: Thanks. I agree with your comment about divide-and-conquer and I edited the question accordingly.  

---

### Answer by username_7 on 2014-10-17. Score: 0

Any question which has recursive answer has iterative answer and vice versa.

Any recursive algorithm can be rewritten in iterative way and vice versa.

Hence, your question doesn't stand good.

> **Comments:**
> **username_0**: The complexity of an algorithm, as I defined it in the question, generally does not remain the same when it is converted from iterative to recursive. For example, the maximum of n elements can be found by an iterative algorithm with O(n) operations, but it can also be found by a recursive algorithm with O(1) operations (one of which is a recursive call). Although finally the runtime of both algorithms is the same, the recursive algorithm is simpler to program because it has less operations.  

---

### Answer by username_8 on 2016-01-11. Score: -2

I am not sure if I correctly understand your notion of "recursive complexity".

Lets (reasonably) Assume a programming language that contains a schema for primitive recursion i.e. in which one can define functions $f$ from

$$
f(0,\vec x) = c(\vec x)\\
f(n+1,\vec x) = g(f(n,\vec x),n,\vec x)
$$

where $c$ and $g$ are previously defined functions. Further let us assume that the basic functions (constants, projections, successor) have $\mathcal{O}(1)$ "recursive complexity" If I understand your definition correctly, then all primitive recursive functions (and thus problems/relations) have $\mathcal{O}(1)$ "recursive runtime". This, I think, can be seen by induction on the build up of recursive functions.

If all my assumptions are met, then the example you are looking for cannot be primitive recursive.

> **Comments:**
> **username_8**: please elaborate on the downvotes  
> **username_9**: From the question, "The recursive runtime of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k<n$ in constant time." . This definition of runtime gives naturally a rise to a complexity measure. This is a fancy way of saying that we do not care about the cost of lower size recursions, but only of the current step. So in your notation, we ask what is the complexity of comuting $g(f(n,x),n,x)$ given an oracle for $f(n,x)$ that has constant runtime.  I didn't downvote you, but this is a year-old answered question and you also misinterpreted a given definition.  
> **username_8**: thanks for your comment. I think I understood the definition. Since $g$ is a prim. rek. function, by induction hypothesis it has runtime $\mathcal{O}(1)$ since $f(n,x)$ is given by the oracle in constant time, evaluating the whole expression takes $\mathcal{O}(1\circ 1)=\mathcal{O}(1)$.  
> **username_10**: You have to use the full complexity for $g$, not its recursive complexity. That's not $O(1)$.  
> **username_8**: ahh, ok... now everything makes sense... thanks for the clarification... I was probably confused by the fact that recursive complexity is not invoked recursively^^ (which is not very celar from the definition imo)  

---

