usar - ¿Se puede cambiar cada recursión a iteración?

ventajas y desventajas de la recursividad

Question

¿ Toda función recursiva es convertible a iteración? ¿Qué característica debe tener una función recursiva para que se implemente utilizando iteración?

He estado tratando de definir la siguiente función usando la iteración, ¡pero parece un no-go! Se supone que debe explorar todos los caminos (nodos) en un laberinto. ¿Alguien puede reescribir esto usando iteraciones? Si no es posible, ¿por qué no?

typedef int[0,99] id_t;
bool visited[id_t];
int path[id_t];
int pathCounter = 0;

struct { 
    id_t id;
    bool free;
    int neighborNode[4];
} nodeMap[id_t];

void findPath(int current){
    visited[current] = true;
    for (i : int[0, 3]){
        if(nodeMap[nodeMap[current].neighborNode[i]].free == true && visited[nodeMap[current].neighborNode[i]] == false && nodeMap[current].neighborNode[i] != -1){
        path[pathCounter] = nodeMap[nodeMap[current].neighborNode[i]].id;
        pathCounter++;
        findPath(nodeMap[current].neighborNode[i]);
        path[pathCounter] = nodeMap[current].id;
        pathCounter++;      
        }
    }
    path[0] = current;
}

Extensión: ¿Es posible convertir la función recursiva mencionada en iteración sin implementar mi propia pila? Una de las respuestas sugería que cada función recursiva de la cola se puede convertir a iteración sin usar una estructura de pila ... si es así, ¿se puede convertir cada función recursiva en recursividad de cola? ¿Cómo?

Answer 1

Al igual que las otras respuestas ya indicadas, es técnicamente posible hacer eso simulando la pila. Pero supongo que no quieres hacer eso. Probablemente desee una solución iterativa sin usar una pila. Si ese es el caso, necesitas tener una función recursiva de cola. AFAIR esa es la única forma posible. Puede volver a escribir cada función recursiva de cola a una imperativa sin simular una pila.

Answer 2

En general, es posible convertir cualquier algoritmo recursivo en bucle. El método es simple: podemos imitar cómo el compilador genera el código para la llamada a la función: ingresar a la función, regresar de la función y continuar la ejecución.

Para convertir una función recursiva en un bucle iterativo, puede:

• Defina un registro, que almacena los argumentos para la función y las variables locales. Esto es equivalente al marco de pila.
• Defina una pila, a la cual registra un empujado. Esto es una analogía de la pila de programas.
• Cuando se llama a una función, crea un registro del valor actual de los argumentos y las variables locales y presiona para apilar.
• Cuando regrese de la función, salga de la pila y sobrescriba el valor actual con el del registro.

Todo el proceso anterior se hace en un ciclo while, que saldrá cuando la pila esté vacía,

Answer 3

Sí, cada función recursiva se puede convertir a una iterativa siguiendo un proceso bastante mecánico.

Recuerde que los compiladores implementan la recursión utilizando una pila, que generalmente se implementa en el hardware de la CPU. Puedes construir tu propia pila de software, hacerla adecuada para mantener el estado de tu función (es decir, sus variables locales), insertar el estado inicial en esa pila y escribir un ciclo while que empuje el nuevo estado a la pila en lugar de hacer una llamada recursiva, mostrando la pila en lugar de regresar, y continuando el proceso mientras la pila no está vacía.

Answer 4

Según http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursion_versus_iteration, todas las funciones definidas recursivamente se pueden convertir a iterativas.

Answer 5

Si tiene una recursión de "cola" simple, entonces puede usar un bucle en su lugar (por ejemplo, función factorial). En funciones más complejas, debe usar una estructura de stack y un while (!stack.empty()) . Sin embargo, si tiene una recursividad bastante compleja, como Towers of Hanoi , Merge Sort e printing truth table , deberá usar una stack con while loop, como anteriormente, pero con una instrucción switch para determinar el estado actual de la llamada.

Recursivo:

void mergeSort(int start, int end)
{
    if (start < end)
    {
         mergeSort(start, (start + end) / 2);
         mergeSort((start + end) / 2 + 1, end);
         Merge(start, end);
    }

}

Iterativo:

void mergeSort()
{
  stack<int> st;
  st.push(1);
  int status;

  while (!st.empty())
  {
      status = st.pop();
      switch (status)
      {
        case 1:
             ....
            break;
        case 2:
             break;
      }
  }
}

Recomiendo este excelente pdf que explica el proceso en detalle.