¿Hay algún problema que tenga solo una solución recursiva?

Question

duplicados posibles:
Is there a problem that has only a recursive solution?
Can every recursion be converted into iteration?
“Necessary” Uses of Recursion in Imperative Languages

¿Existe un problema que tiene sólo una solución recursiva, es decir, un problema que tiene una solución recursiva, sino una solución iterativa aún no se ha encontrado, o mejor aún, ha demostrado ser inexistente (obviamente, esto no es una repetición de cola)?

Answer 1

El Ackermann function no se puede expresar sin recursividad

Answer 2

Todos los problemas no np-completos se pueden resolver con solo secuencia, decisión e iteración. La recursividad no debería ser requerida, aunque generalmente simplifica enormemente el problema.

Answer 3

reemplaza las llamadas de función con argumentos de empuje en una pila, y regresa con estallar de la pila, y has eliminado la recursión.

Editar: en respuesta a "por medio de una pila no disminuye los costes de espacio"

Si un algoritmo recursivo puede funcionar en el espacio constante, se puede escribir de una manera recursiva de cola. si está escrito en formato recursivo de cola, entonces cualquier compilador decente puede colapsar la pila. Sin embargo, esto significa que el método "convertir funciones llama a apilar paquetes explícitos" también requiere espacio constante también. Como ejemplo, vamos a tomar factorial.

factorial:

def fact_rec(n): 
    ' Textbook Factorial function ' 
    if n < 2: return 1 
    else:  return n * f(n-1) 


def f(n, product=1): 
    ' Tail-recursive factorial function ' 
    if n < 2: return product 
    else:  return f(n-1, product*n) 

def f(n): 
    ' explicit stack -- otherwise same as tail-recursive function ' 
    stack, product = [n], 1 
    while len(stack): 
     n = stack.pop() 
     if n < 2: pass 
     else: 
      stack.append(n-1) 
      product *= n 
    return product 

porque el stack.pop() sigue el stack.append() en el bucle, la pila no tiene más de un elemento en él, y por lo que cumple con la constante de espacio requisito. Si imagina usar una variable de temperatura en lugar de una pila de 1 de longitud, se convierte en su algoritmo factorial iterativo estándar.

Por supuesto, hay funciones recursivas que no se pueden escribir en formato recursivo de cola. Todavía puede convertir a formato iterativo con algún tipo de pila, pero me sorprendería si hubiera garantías sobre la complejidad del espacio.

Answer 4

Todo se reduce a la cantidad de líneas de código se va a tomar para resolver el problema ...

una lista de todos los archivos en la carpeta C: \ utilizando la recursividad y luego, sin. Claro que puedes hacerlo de las dos maneras, pero una forma será mucho más simple de entender y depurar.

Answer 5

No. Recursion no es más que una pila y puede lograr los mismos resultados implementando una pila explícitamente.

Esa puede no ser una respuesta especialmente satisfactoria, pero tendría que hacer una pregunta mucho más específica para obtener una mejor respuesta. Por ejemplo, la teoría dicta que en los niveles de computación existe una gran diferencia en el rango de problemas que pueden resolverse si se tiene un ciclo while versus solo un ciclo (tradicional) para loops.

Puse "tradicional" allí porque realmente significan bucles que se repiten un cierto número de veces, mientras que el estilo C para los bucles (...; ...; ...) son bucles while disfrazados.

Answer 6

En la programación, la recursión es realmente un caso especial de iteración, en el que se utiliza la pila de llamadas como un medio especial de almacenamiento de estado.Puede reescribir cualquier método recursivo para que sea iterativo. Puede ser más complicado o menos elegante, pero es equivalente.

En matemáticas, hay ciertos problemas que requieren técnicas recursivas para llegar a una respuesta - algunos ejemplos son las raíces para encontrar (Newton's Method), primos informáticos, optimización gráfica, etc. Sin embargo, incluso en este caso, no es sólo una cuestión de cómo se diferencian los términos "iteración" y "recursión".

EDITAR: Como han señalado otros, existen muchas funciones cuya definición es recursiva - ej. el Ackermann function. Sin embargo, esto no significa que no se puedan computar utilizando construcciones iterativas, siempre y cuando tengas un conjunto de operaciones completo y una memoria ilimitada.

Answer 7

Se puede definir una Turing Machine sin recursividad (¿verdad?) Así que la recursividad no es necesario para un lenguaje que sea Turing-complete.

Answer 8

En respuesta al Ackermann function answer, este es un problema muy sencillo de convertir la llamada a la pila en una pila real. Esto también muestra un beneficio de la versión iterativa.

en mi plataforma (Python 3.1rc2/Vista32) la versión iterativa calcula ack (3,7) = 1021 fine, mientras que la versión recursiva stackflows fluye. NB: no stackoverflow en Python 2.6.2/Vista64 en una máquina diferente, por lo que parece más bien dependiente de la plataforma,

(wiki de la comunidad porque esto es realmente un comentario a otra respuesta [si solo se admiten comentarios formato de código ....])

def ack(m,n): 
    s = [m] 
    while len(s): 
    m = s.pop() 
    if m == 0: 
     n += 1 
    elif n == 0: 
     s.append(m-1) 
     n = 1 
    else: 
     s.append(m-1) 
     s.append(m) 
     n -= 1 
    return n