8
$\begingroup$

I'm not sure if my wording is entirely correct, but I was just wondering if every recursive formula can be turned into an explicit formula.

I am asking this because various sources online gives me opposite answers. Although, one thing I have noticed is that every source likes to use different words other than "formula", like "expression" and such.

According to wiki, "Although not all recursive functions have an explicit solution"

So I guess another part of my question is : What difference is it when people say recursive function, expression, formula, etc. (if there is any)

But yeah, I have seen a stackoverflow post saying that every recursion can be turned into an iteration, and doesn't this also mean everything can be explicitly defined?

  • 0
    Can the function which maps $n$ to the number of steps required for the Goodstein sequence of $n$ to terminate (see https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Application_to_computable_functions) be given "explicitly"? It grows very fast, and the fact that it is a total function cannot be proved in Peano Arithmetic.2012-10-19

2 Answers 2

3

You are reading about two different things. There are recursive functions in math, and there are recursive functions in computer programming. Programming is a form of math, but never mind that. In general, a recursive function where $f(n) = g(n, f(n-1), f(n-2), \ldots)$ can not always be converted to an explicit form. On the other hand, a recursive function in a computer program can be converted to a non-recursive (iterative) function. This is due to a rather trivial solution where the program's call stack is imitated in an iterative function.

  • 0
    The [Ackermann function](https://en.wikipedia.org/wiki/Ackermann_function) comes to mind.2013-09-03
2

This question is not "well-formed".

Recursion is a way (actually several ways, as there are many formalisms containing different recursion schemes) to describe a function (or a collection of functions or some other structures..).

So, what you are actually asking, is whether or not it is possible to describe functions that can be described "by means of recursion" within some other formalism. You fail to specify the "other formalism" as well as the "recursion-formalism" (of which recursion will be only a part).

Some formalisms that do not contain recursion can express exactly the same functions as some other "recursive formalisms" eg.:

  • LOOP computable functions vs. primitive recursive functions
  • WHILE computable functions vs. $\mu$-recursive functions

However, if you aim at asking whether or not every formalism (that describes a family of functions) can be replaced by an equivalent "non-recursive" formalism, then we have to:

  • Define what we mean by a formalism
  • What we mean by equivalent
  • And maybe ask ourselves why we would want to get rid of recursion in the first place ;)

I think that in most cases (given proper definitions of the above) the answer would be 'yes' but at the cost of some other complexity of the formalism (like additional quantifiers or other advanced constructs)