Puede cada recursiva fórmula se expresa de forma explícita?

Question

No estoy seguro de si mi redacción es del todo correcto, pero me estaba preguntando si cada fórmula recursiva puede ser convertido en una fórmula explícita.

Yo estoy pidiendo esto porque varias fuentes en línea me da opuesto respuestas. Aunque, una cosa que he notado es que cada fuente gusta usar diferentes palabras que no sean "fórmula", como "expresión" y tal.

Según la wiki, "a Pesar de que no todas las funciones recursivas tienen una solución explícita"

Así que supongo que otra parte de mi pregunta es : ¿Cuál es la diferencia cuando las personas dicen función recursiva, de expresión, de fórmula, etc. (si hay alguna)

Pero sí, he visto un stackoverflow post diciendo que cada recursividad puede ser convertido en una iteración, y no esto también significa que todo puede ser definido explícitamente?

Answer 1

Usted está leyendo acerca de dos cosas diferentes. Hay funciones recursivas en matemáticas, y hay funciones recursivas en la programación de computadoras. La programación es una forma de matemáticas, pero eso no importa. En general, una función recursiva, donde $f(n) = g(n, f(n-1), f(n-2), \ldots)$ no siempre se puede ser convertido a una forma explícita. Por otro lado, una función recursiva en un programa de ordenador puede ser convertido a un no-recursivo (iterativo) de la función. Esto es debido a bastante trivial solución en la que el programa de la pila de llamadas es imitado en un proceso iterativo de la función.

Answer 2

Esta pregunta no es "bien formado".

La recursividad es una forma (de hecho varias maneras, ya que hay muchos formalismos que contienen diferentes recursividad esquemas) para describir una función (o un conjunto de funciones o algunas otras estructuras..).

Así, lo que en realidad está pidiendo, es si es o no es posible describir las funciones que pueden ser descritas "por medio de la recursividad" dentro de algún otro formalismo. No especificar el "otro formalismo" así como la "recursividad-formalismo" (de los que la recursividad va a ser sólo una parte).

Algunos formalismos que no contienen la recursividad puede expresar exactamente las mismas funciones como algunos otros "recursiva formalismos" ej.:

• BUCLE de funciones computables vs primitivas de funciones recursivas
• MIENTRAS que las funciones computables vs $\mu$-funciones recursivas

Sin embargo, si tu objetivo en la pregunta si o no todo formalismo (que describe una familia de funciones) puede ser sustituido por un equivalente de la "no-recursivo" formalismo, entonces tenemos que:

• Definir lo que entendemos por un formalismo
• Lo que queremos decir por el equivalente
• Y tal vez preguntarnos por qué nos quieren deshacerse de la recursividad en el primer lugar ;)

Creo que en la mayoría de los casos (dado definiciones adecuadas de los anteriores), la respuesta sería "sí", pero en el costo de algunos otros de la complejidad del formalismo (como adicional cuantificadores o avanzada construcciones)