recursion - iterativos - algoritmos recursivos ejemplos

¿Qué funciones recursivas no se pueden reescribir utilizando bucles?

Question

Hasta donde yo sé, la mayoría de las funciones recursivas se pueden reescribir utilizando bucles. Algunos quizás sean más difíciles que otros, pero la mayoría se pueden reescribir.

¿Bajo qué condiciones se vuelve imposible reescribir una función recursiva utilizando un bucle (si existen tales condiciones)?

Answer 1

Cuando utiliza una función recursivamente, el compilador se ocupa de la administración de la pila, que es lo que hace posible la recursión. Todo lo que puede hacer recursivamente, lo puede hacer administrando una pila usted mismo (para la recursión indirecta, solo tiene que asegurarse de que sus diferentes funciones compartan esa pila).

Entonces, no, no hay nada que se pueda hacer con la recursión y eso no se puede hacer con un bucle y una pila .

Answer 2

En SICP , los autores desafían al lector a encontrar un método puramente iterativo para implementar el problema del "conteo de conteo" ( este es un ejemplo del Proyecto Euler).

Pero ya se dio la respuesta estricta a su pregunta: los bucles y las pilas pueden implementar cualquier recursión.

Answer 3

La recursión indirecta todavía es posible convertir a un ciclo no recursivo; solo comience con una de las funciones y alinee las llamadas a las demás hasta que tenga una función recursiva directa, que luego se puede traducir a un bucle que use una estructura de pila.

Answer 4

No sé de ejemplos donde las funciones recursivas no se pueden convertir a una versión iterativa, pero los ejemplos poco prácticos o extremadamente ineficientes son:

• cruce de árboles

• Fast Fourier

• quicksorts (y algunos otros iirc)

Básicamente, cualquier cosa en la que tengas que empezar a realizar un seguimiento de estados potenciales ilimitados.

Answer 5

No se trata tanto de que no puedan implementarse mediante bucles, sino de que la forma en que funciona el algoritmo recursivo es mucho más clara y concisa (y en muchos casos matemáticamente demostrable) de que una función es correcta.

Se pueden escribir muchas funciones recursivas para que sean recursivas de bucle de cola, que se pueden optimizar para un bucle, pero esto depende tanto del algoritmo como del idioma utilizado.

Answer 6

Se puede hacer que cualquier función recursiva itere (en un bucle) pero necesita usar una pila para mantener el estado.

Normalmente, la recursividad de cola es fácil de convertir en un bucle:

A(x) {
  if x<0 return 0;
  return something(x) + A(x-1)
}

Se puede traducir a:

A(x) {
  temp = 0;
  for i in 0..x {
    temp = temp + something(i);
  }
  return temp;
}

Otros tipos de recursión que pueden traducirse en recursividad de cola también son fáciles de cambiar. El otro requiere más trabajo.

El seguimiento:

treeSum(tree) {
  if tree=nil then 0
  else tree.value + treeSum(tree.left) + treeSum(tree.right);
}

No es tan fácil de traducir. Puede eliminar una parte de la recursión, pero la otra no es posible sin una estructura para mantener el estado.

treeSum(tree) {
  walk = tree;
  temp = 0;
  while walk != nil {
    temp = temp + walk.value + treeSum(walk.right);
    walk = walk.left;
  }
}

Answer 7

Siempre puede usar un bucle, pero puede que tenga que crear más estructura de datos (por ejemplo, simular una pila).

Answer 8

Todos pueden escribirse como un bucle iterativo (pero algunos aún pueden necesitar una pila para mantener el estado anterior para iteraciones posteriores).

Answer 9

Un ejemplo que sería extremadamente difícil de convertir de recursivo a iterativo sería la función de Ackermann .

Answer 10

Cada función recursiva se puede implementar con un solo bucle.

Solo piensa lo que hace un procesador, ejecuta las instrucciones en un solo ciclo.