¿Se pueden modelar todos los algoritmos iterativos de forma recursiva y viceversa?

Esta respuesta es básicamente una toma de nivel inferior de la respuesta de Anders.

Tengo que estar (algo) en desacuerdo con la respuesta de Isaac.
Creo que se puede decir que el ensamblaje (bien estructurado) presenta recursividad, aunque todo es más loco en el ensamblaje.

De hecho, creo que el código de ensamblaje será algo útil para 1 / probar el punto que acabo de hacer 2 / explicar el “enlace” entre el código iterativo y el código recursivo, lo que me permitirá probar que 3 / cualquier algoritmo puede implementarse usando cualquier paradigma.

Esta es una implementación del algoritmo factorial recursivo ingenuo en el ensamblaje nasm (lo siento, es bastante largo, y lo siento si no es perfecto, mi ensamblaje está un poco oxidado y tengo que hacer que este código sea lo más simple posible de entender):

  scanf externo
 impresión externa

 principal global
 principal:
         empuje 0;  El valor scanf se modificará para obtener nuestro número                     
         empujar esp;  La dirección de ese valor                                         
         empujar scanfstring;  La cadena "% d"                                                   
         llamada scanf
         pop eax;  Aquí el resultado está convenientemente a la derecha                      
         pop eax;  colocar en la pila, no es necesario reventarlo                             

         llamada factorial;  Llamando factorial con nuestro argumento                               

         empujar eax
         push printfstring
         llamar a printf;  Imprimir el resultado                                               
         pop eax
         pop eax

         mov eax, 1;  Saliendo (solo funciona en Linux)                                     
         int 80h

 factorial:
         mov ecx, [esp + 4];  Obteniendo el argumento                                              

         prueba ecx, ecx;  Comprobando por 0                                                    
         jz on_zero

         sub ecx, 1
         empujar ecx
         llamada factorial;  Llamada recursiva con argumento-1                                    
         pop ecx

         mov ecx, [esp + 4];  Calculando el resultado                                              
         imul eax, ecx
         jubilado
 en cero:
         mov eax, 1;  Devuelve 1 si el argumento es 0                                         
         jubilado

 sección .rodata
 scanfstring: db '% d', 0
 printfstring: db '% d', 10,0 

En pseudocódigo, esto lee

  factorial (valor)
   valor de retorno * factorial (valor - 1) 

Primero, la función factorial es de hecho recursiva, y no recursiva de cola, completamente recursiva.

Segundo, este código permite ver el enlace (y por lo tanto la “equivalencia”) entre el código iterativo y el código recursivo: la pila.
De hecho, creo que sería justo decir que el ensamblaje no admite totalmente el paradigma iterativo (ya que a menudo tiene pocas construcciones de bucle real) ni el paradigma recursivo (ya que uno tiene que manipular la pila uno mismo), y esto permite exponer lo que el Las construcciones están hechas de.

La parte más importante del código de ensamblaje anterior es la llamada recursiva a factorial. Se puede ver que consiste en empujar un valor a una pila implícita, llamar factorial y luego extraer el valor de la pila. Esta pila implícita es lo único que permite que algunos algoritmos sean más fáciles de implementar de forma recursiva que iterativa.
Sin embargo, uno siempre puede implementar un algoritmo recursivo iterativamente usando una pila explícita.

Aquí está el equivalente iterativo C exacto de este algoritmo, usando una pila explícita (muy básica):

 #include  int main() { int stack[1000]; // This can overflow, but it's just an example int *stack_ptr = stack; int current_value; scanf("%d", &current_value); while (current_value > 0) { *stack_ptr = current_value; current_value--; stack_ptr++; } int result = 1; while (stack_ptr != stack) { stack_ptr--; result *= *stack_ptr; } printf("%d\n", result); } 

Ahora, hasta donde sé, básicamente nunca vale la pena usar una pila explícita en lugar de una función recursiva (aunque en realidad he visto esta técnica utilizada en la vida real, estaba en el medio de una función ya gigantesca y el programador aparentemente se opuso a dividir su código en varias funciones …).

Además, este es un ejemplo simple, pero si una función es recursiva en varios lugares, la pila explícita tendrá que ser más compleja ya que el segundo ciclo while tendrá que dividirse en varias partes (usando ifs o una instrucción switch) y stack tendrá que especificar qué parte debe procesar cada pieza de datos.

Básicamente, una función recursiva de cola es una función recursiva que no usará su pila para nada útil, por lo que la pila puede dejarse sin usar para acelerar ligeramente la función y evitar desbordamientos de stock.