¿Cómo hace una computadora la recursividad desde el punto de vista del hardware?

Tuve un maestro que tomó clases para C, C ++ y Java. Explicó la recursividad de esta manera. En mi opinión, este método es la forma más fácil de entenderlo desde el punto de vista del hardware o para un lego.

Tenía una pizarra blanca magnética y llevaba un montón de hojas con una simple función factorial recursiva impresa en letras grandes. Luego escribió una función principal en la pizarra que llamó a esta función y mostró el resultado y pegó la hoja de la función debajo de la función principal. Luego dibujó una flecha pasando los argumentos de la función principal a la función factorial.

La función factorial obviamente se llamaba a sí misma, por lo que pegó otra copia de esa función sobre ella y pasó los nuevos valores de argumento. Luego pegó otra copia de la función y repitió el mismo procedimiento hasta que se logró el caso base. Una vez allí, devolvió esos valores a la llamada de función anterior representada a través de flechas y eliminó esa hoja de papel. Esto lo hizo hasta que llegó a la última hoja. Los valores fueron devueltos a la función principal. Así es más o menos como se veía la pizarra justo cuando el programa estaba a punto de llegar al caso base:

Vamos a entenderlo de esta manera. Cada hoja de papel se refiere a una ubicación de memoria separada donde se realiza cada llamada de función. A medida que se llama a la función, se le asigna nueva memoria y, a medida que se ejecuta la función, se libera esa memoria. Luego, se ejecuta la ubicación de memoria que contiene la llamada a la función anterior y se repite el mismo procedimiento hasta que se abordan todas las funciones recursivas y el programa finaliza. Esto sigue el mecanismo de pila o el enfoque de último en entrar, primero en salir.

Perdón por el diagrama feo.

Trataré de explicar el proceso de la manera más simple posible.

• El procesador maneja diferentes programas usando una pila de programas.
• De acuerdo con la pila de programas, cada función / procedimiento tendrá su propio espacio privado en la pila, que se asignará en la llamada a la función y se desasignará al regresar.
• El concepto anterior de tener un espacio privado asignado en la pila hace que sea simple tener funciones recursivas, sin la necesidad de ninguna lógica compleja.

Consideremos un programa factorial simple que se muestra a continuación:

  #include 

 int rfact (int n) {
     resultado int;
     si (n <= 1)
         resultado = 1;
     más
         resultado = n * rfact (n-1);

     resultado de retorno;
 }

 int main () {
     printf ("Hecho:% d \ n", rfact (4));
     devuelve 0;
 }

Compilando lo anterior usando el comando gcc -S -O0 recursion.c e inspeccionando el código de ensamblaje generado (recursion.s), deberíamos obtener algo como lo siguiente:

  _rfact: ## @rfact
 ## BB # 0:
     pushl% ebp
     movl% esp,% ebp
     subl $ 24,% esp
     movl 8 (% ebp),% eax
     movl% eax, -4 (% ebp)
     cmpl $ 1, -4 (% ebp)
     jg LBB0_2
 ## BB # 1:
     movl $ 1, -8 (% ebp)
     jmp LBB0_3
 LBB0_2:
     movl -4 (% ebp),% eax
     movl -4 (% ebp),% ecx
     subl $ 1,% ecx
     movl% ecx, (% esp)
     movl% eax, -12 (% ebp) ## Derrame de 4 bytes
     calll _rfact
     movl -12 (% ebp),% ecx ## Recarga de 4 bytes
     imull% eax,% ecx
     movl% ecx, -8 (% ebp)
 LBB0_3:
     movl -8 (% ebp),% eax
     addl $ 24,% esp
     popl% ebp
     jubilado

El código original es mucho más largo, pero acabo de pegar el código para rfact . Si tiene una idea básica de lo que significan varias instrucciones, puede inferir que, de hecho, no se utiliza una lógica especial para tratar la recursividad.

Espero que esto ayude.

Para la recursividad normal (sin cola), el código se genera para crear un nuevo marco de pila (resta del puntero de pila) para cada llamada recursiva. Para la recursión de cola, esta asignación adicional se evita reutilizando el marco de pila actual. Por lo tanto, el código recursivo de cola es más eficiente e inmune a los desbordamientos de la pila que a menudo afectan el código recursivo no de cola.