# Can you tell if you have escaped from a recursive definition?

Most people define a function, f(n) on N recursively. I think I can calculate f(n) without dealing with f(n-r) for any 0 < r < n. How do I know that my method isn't still going through the same calculations needed to find f(n-1) (or whatever previous terms are required to find f(n) recursively) -- ?

1. If my method takes many fewer calculations than the recursive way of calculating it does that show that I am not relying on f(n-r) for any 0 < r < n? What would "many fewer" have to mean for this to be significant?

2. The number of calculations my method takes still depends on n, just like the recursive way of calculating f(n), does that alone mean that the methods are pretty much the same?

3. If my method takes the same number (or more) calculations than recursive way of calculating f(n) is there any other way of telling if my method is not, in some way, duplicating the recursive way of calculating f(n)?

Examples:

f(n) is recursively defined to be f(n) = f(n-1) + 1 and f(1) = 1 Then f(n) = n. Clearly, f(n) = n is a much faster way to find f(2876) rather than counting up from 1.

f(n) is recursively defined to be f(n) = f(n-1) + f(n-2) This is a linear recurrence and has a closed-form solution. $F\left(n\right) = {{\varphi^n-(1-\varphi)^n} \over {\sqrt 5}}={{\varphi^n-(-1/\varphi)^{n}} \over {\sqrt 5}}\,$ (from wikipedia)

$S(n,k)=kS(n−1,k)+S(n−1,k−1)$ with $S(n,n)=S(n,1)=1$ (Stirling numbers of the second kind) Almost seems like it's a linear recurrence... but we need to know about k-1. These numbers are defined as "the number of ways to partition a set of n objects into k groups" so, if I have written a few programs to find S(n,k) from that definition I want to know if I "must" find the values in the linear recurrence along the way...

But, I was trying to keep it more general to make it interesting?

One more example:

$C(n,k)=C(n−1,k)+C(n−1,k−1)$ with $C(n,n)=C(n,1)=1$ but $C(n,k) = \frac{n!}{k!(n-k!)}$, most people like the 2nd one better of you want to look at large values of n and k>1...

-
Your question is much too vague. Can you give an actual example? –  Jacques Carette Mar 28 '10 at 2:54
The Fibonacci example is a bad one. The "naive" way of computing the power of something is to multiply it by itself over and over again, which is just a hidden form of the Fibonacci recursion if you do it exactly and requires you to compute a lot of digits of phi if you don't do it exactly. A much better algorithm to compute large Fibonacci numbers is to use a variant of binary exponentiation, which is still essentially recursive but only requires that you compute logarithmically many previous Fibonacci numbers. –  Qiaochu Yuan Mar 28 '10 at 3:46
The last example you give has the same problem: factorials are themselves defined by a recursion. While it's useful to know that it's easy to approximate the size of a factorial, if you know a way to compute large factorials exactly and quickly then you can use Wilson's theorem as a primality test, and nobody has been able to do this (yet). –  Qiaochu Yuan Mar 28 '10 at 4:04
Qiaochu, I think the question is not about the particular examples. Rather, the question (which I voted up), is about how in general are we to compare various methods of computing the same function? One very robust way, which I explain in my answer, is to use the measures of computational complexity. –  Joel David Hamkins Mar 28 '10 at 5:05
The paper you posted is on the question I was trying to ask. –  S. Donovan Mar 28 '10 at 5:17

## 3 Answers

You inquire about comparing your algorithm to a given recursive algorithm, but the more fundamental question would seem to be how good is your algorithm just by itself?

There are numerous ways to measure the efficacy of a computational algorithm using the ideas of computational complexity. That is, you should measure the complexity of your algorithm by the intensely studied classes of P, NP, PSPACE, EXP, and so on. That is, if you have an algorithm to calculate a function f, the important thing to look at is where does your algorithm sit with respect to these complexity measures: is it polynomial time? exponential time? Is there a nondeterministic polynomial time algorithm? Is there a PSPACE algorithm?

You inquire about comparing your algorithm to a given recursive algorithm. For such a comparison, one should use the measures of complexity theory. If these two algorithms have the same computational complexity, then they are equivalent by these measures, even if your algorithm does not exactly amount to performing the same computation, and the two methods would be equivalent in terms of their computational cost. But if one algorithm finds itself in a lower complexity classification, then it will inevitably be superior in the general case.

-
I'm not really worried about how complex it it or how long ti would take expect as far as that might tell me if the algorithms are in some sense the "same" I guess I'm looking for ways to define when algorithms are the same. Is that taken up in computational complexity theory? –  S. Donovan Mar 28 '10 at 3:58
This is a deep philosophical question, and several titans in computability/complexity theory have come down on the side of saying that there is no answer to the question of when are two algorithms the same. See this essay research.microsoft.com/en-us/um/people/gurevich/opera/192.pdf by Blass, Dershowitz and Gurevich. –  Joel David Hamkins Mar 28 '10 at 4:07
Thank you for that link. –  S. Donovan Mar 28 '10 at 5:13

I guess it's worth saying this in an answer: I don't think this is a meaningful question. Consider the function defined recursively by $f(0) = 1, f(n+1) = 2 f(n)$. Clearly $f(n) = 2^n$ for all $n$. You shouldn't consider this formula an "escape" from the recursive definition, for the very simple reason that the exponential function is usually defined by this very recursion! (One can, of course, do something incredibly silly like define $2^n$ to be $e^{n \ln 2}$. Whether you think this constitutes an "escape" from the recursive definition is up to you, but what it doesn't constitute is a fast method to compute powers of two.)

What you can ask for, instead, is an algorithm faster than the naive one above. There is, in fact, such an algorithm; it goes by the name binary exponentiation or exponentiation by squaring, and it basically works by replacing the recursion $f(n+1) = 2f(n)$ by a pair of recursions $$f(2n) = f(n)^2, f(2n+1) = 2f(n)^2.$$

Does this constitute an "escape" from the recursive definition? I don't know; it still requires that you compute some smaller powers of two, just not as many.

-
So are you saying that it would never make sense to talk about two "different" ways of calculating the same function? This is very helpful since I can see the recursion built in to the examples I have so far. –  S. Donovan Mar 28 '10 at 4:01
No, that's not what I'm saying; I guess you should just read JDH's response to your comment on his answer. –  Qiaochu Yuan Mar 28 '10 at 4:10
FYI: The sentence beginning with "clearly" is false. Suggested correction: f(0) = 1. –  aorq Mar 28 '10 at 5:29
Whoops! Thanks. –  Qiaochu Yuan Mar 28 '10 at 5:50

My answer will forcibly be vague, as your question is quite vague. One reminder: iteration is essentially equivalent to recursion (i.e. you can simulate one with the other). So either your method is made up of only arithmetic operations and branching (but no loops, recursion, throwing exceptions, gotos, i.e. no control structures), in which case there is no hidden recursion, OR it contains some control structure which may well be 'hiding' the equivalent of a recursive definition.

The number of operations isn't going to help you in a substantial way, at least not unless you can bound them independent from 'n'. If your number of computations still depends on 'n', then whether you get an improvement depends on the actual dependence on 'n'. You can write a bad recursive search in ordered data in $O(n)$ and a good one in $O(\ln n)$, so details really do matter.

-
I tried to add some examples, but this is still helpful. Thanks. –  S. Donovan Mar 28 '10 at 3:19