1

is there a function that can be proved is only defineable recursively? the converse seems to be trivially false, i.e. every iteritive function is trivially defined recursively with 0 for coefficients for antecedal terms, how ever can a function such as $f(x)=x$ be defined non trvialy recursive in $\mathbb R$? $x_n = x_{n-1}+1$ defines it recursively over $\mathbb N$.

Is there a list of known ways that functions can be defined? for example consider followings:

$f(x)= \text{some algebraic expression , finite or infinite}$ : algebraicly defined

$x_{n+1}= \text{some algebraic expression involving }x_n, x_{n-1}, \cdots$ : recursively defined

$y : \text{if there are no 2 in decimal digits of x then 1 else 0} $ : defined by testing

or is there a reason not to bother with how functions defined?

jimjim
  • 9,675
  • n! can't be written as a function of 1 variable returning an exact result. You either use approximation or recursion to find the value. – NoChance Jan 07 '16 at 03:47
  • @NoChance not really, just multiply the numbers from 1 to n and you have the result. Even Fibonacci can be written as a function of 1 variables. Actually the multiplication of 1 to n is a better implementation of n! Than the recursive definition. The text books use n! As a bad example to introduction into recursion. – jimjim Jan 07 '16 at 04:18
  • I will not argue much at this point, but if you are multiplying numbers, one could still say that you are 'implicitly' using recursion. The fact that Fibonancci can be expressed in a function of 1 variable does not mean that every recursive expression can be generalized, no such function is known for n! to my knowledge. It is true that "Linear homogeneous recurrence relations with constant coefficients" can be turned into a " characteristic polynomial" as the following link suggests but that is not a generalization for all recurrence relation types. – NoChance Jan 07 '16 at 04:35
  • I added the link here since I have exceeded the max. allowed length of a comment....https://en.wikipedia.org/wiki/Recurrence_relation#Linear_homogeneous_recurrence_relations_with_constant_coefficients – NoChance Jan 07 '16 at 04:36
  • @NoChance look up gamma function – jimjim Jan 07 '16 at 04:46
  • I will, thanks. – NoChance Jan 07 '16 at 04:48
  • @Arjang Did you understood my answer? E.g. you can not write an iterative version of the Ackermann function with a for-loop where the start, end, and increment values stay constant during the loop. This beast is not primitive recursive/LOOP computable, but $\mu$-recursive/WHILE/GOTO computable. – mvw Jan 09 '16 at 06:06
  • @mvw : my question is not about computing theory, for example factorial can be defined recursively or as gamma function, can it be shown that Ackerman fuction can not be defined without requiring it's own previous values ? – jimjim Jan 09 '16 at 06:28
  • @Arjang What you aim for seems to be closed-form expressions, thus a mathematical expression that can be evaluated in a finite number of operations.. Have also a look at Dealing with non-closed-form expressions, The theory of computation deals with what can be calculated with finite many operations and memory. – mvw Jan 09 '16 at 06:42

2 Answers2

3

I am not sure what you permit as non recursive function definitions, you seem to label them as iterative. That sounds like a loop.

Now there are simple loops with fixed start and fixed end. Those can not compute every computable function, they can deliver the primitive recursive functions only.

This would be the case, where I would look for a function that can not be computed that way, it will have a recursive definition which does. See here for examples.

If the loop parameters can change during the loop, or if a while loop is used then you get all computable functions. So you will not find an example.

This is the area of recursion theory or theory of computation.

There is a nice model, called register machines, which is one of the simplest assembler languages possible, just adding, substraction and conditional jump on test for zero. That is enough to compute everything a Turing machine could do, only for natural numbers instead of words.

mvw
  • 34,562
0

In principle it is possible to "simulate" a recursive function by implementing a stack.

Robert Israel
  • 448,999
  • Hi Robert, I did not mean to ask a computing question, by recursive I mean something that uses a relation to self similarity in some way. Eg the next Fibonacci number is related to two previous fib numbers, yet it here is a function that generates all the fib numbers without relying on the knowledge of previous numbers. Similar thing for recursive definition of factorial works with gamma function. So it seems that although it might be difficult to have a recursive function defined non recursively with some effort, but is thee a case where it is impossible? – jimjim Jan 07 '16 at 04:52