Lenguaje ensamblador - Recursión

La recursión (Recursion) es la técnica en la que una función se llama a sí misma. Implementar recursión en ensamblador requiere gestionar correctamente los marcos de pila; cada llamada tiene copias independientes de parámetros y variables locales.

Principio de recursión y marco de pila

El núcleo de la recursión radica enCada llamada crea un nuevo marco de pila, guardando el estado actual en la pila.

Cada llamada recursiva empuja los parámetros, la dirección de retorno y las variables locales a la pila. Cuando la recursión termina, los marcos de pila se desapilan capa por capa; cada capa obtiene el resultado de su subllamada y completa el cálculo.

Elementos de la recursión	Descripción	Implementación en ensamblador
Condición de terminación	Evitar recursión infinita	Comparación condicional + saltos je/jg
Llamada recursiva	La función se llama a sí misma	Instrucción call
Guardado de estado	Estado independiente en cada llamada	Marco de pila (push ebp; mov ebp, esp)
Paso de parámetros	Parámetros diferentes en cada llamada	Empujar parámetros a la pila con push

Aunque la recursión produce un código elegante, en ensamblador cada llamada tiene un costo de pila considerable. Una profundidad de recursión demasiado grande puede provocar desbordamiento de pila (Stack Overflow). En escenarios sensibles al rendimiento, considera reescribir la recursión como un bucle.

Implementación recursiva del factorial

Ejemplo

; Ruta del archivo: factorial.asm
; Calcula recursivamente el factorial: n! = n * (n-1)!

section .data
n dd 5 ; Calcula 5!
result dd 0
output_msg db 'Factorial result: '
output_len equ $ - output_msg
newline db 0xA

section .bss
result_str resb 12

section .text
global _start

_start:
; Llama a factorial(5)
push dword [n] ; Empuja el parámetro n
call factorial
add esp, 4 ; Limpia los parámetros
; eax = 120 (5!)

mov [result], eax

; Muestra el resultado
mov eax, 4
mov ebx, 1
mov ecx, output_msg
mov edx, output_len
int 0x80

; Salida numérica simple (solo para demostración de un dígito)
mov eax, [result]
; Aquí se simplifica el proceso
mov ebx, eax
mov eax, 1
int 0x80

; Procedimiento: factorial(n)
; Entrada: [ebp+8] = n
; Salida: eax = n!
factorial:
push ebp ; Guarda el marco de pila anterior
mov ebp, esp ; Establece un nuevo marco de pila

mov eax, [ebp + 8] ; Obtiene el parámetro n
cmp eax, 1 ; n <= 1 ?
jg recurse ; n > 1, continuar recursión

; Condición de terminación: n <= 1, retorna 1
mov eax, 1
jmp factorial_end

recurse:
; Guarda el valor actual de n (el registro será alterado por la llamada recursiva)
push eax ; Guarda n

; Llamada recursiva a factorial(n-1)
dec eax ; n - 1
push eax ; Parámetro: n-1
call factorial ; Llamada recursiva
add esp, 4 ; Limpia los parámetros

; Restaura n
pop ebx ; ebx = n

; eax = n * factorial(n-1)
mul ebx ; edx:eax = eax * ebx
; Para n pequeño, edx es 0, el resultado está completamente en eax

factorial_end:
pop ebp ; Restaura el marco de pila anterior
ret

Proceso completo de pila de llamadas y retorno para el cálculo recursivo de factorial(5):

A continuación se muestra el proceso de llamada en versión de texto:

factorial(5)
  -> 5 * factorial(4)
       -> 4 * factorial(3)
            -> 3 * factorial(2)
                 -> 2 * factorial(1)
                      -> 1  (终止条件)
                 <- 1 * 2 = 2
            <- 2 * 3 = 6
       <- 6 * 4 = 24
  <- 24 * 5 = 120

Implementación recursiva de Fibonacci

Ejemplo

; Ruta del archivo: fibonacci.asm
; Calcula recursivamente la secuencia de Fibonacci: fib(n) = fib(n-1) + fib(n-2)

section .data
n dd 10 ; Calcula fib(10)

section .text
global _start

_start:
; Llama a fib(10)
push dword [n]
call fibonacci
add esp, 4
; eax = fib(10) = 55

mov ebx, eax ; Código de salida = 55
mov eax, 1
int 0x80

; Procedimiento: fibonacci(n)
; Entrada: [ebp+8] = n
; Salida: eax = fib(n)
fibonacci:
push ebp
mov ebp, esp

mov eax, [ebp + 8] ; Obtiene el parámetro n

; Condición de terminación: si n <= 1, retorna n
cmp eax, 1
jg fib_recurse ; n > 1, se necesita recursión
; n <= 1：fib(0)=0, fib(1)=1
jmp fib_end

fib_recurse:
; ★ Nota: la recursión tiene dos ramas, hay que gestionar la pila con cuidado
push ebx ; Guarda ebx (se usará para guardar resultados intermedios)

; Calcula fib(n-1)
mov eax, [ebp + 8]
dec eax ; n - 1
push eax
call fibonacci
add esp, 4
mov ebx, eax ; ebx = fib(n-1) (¡guarda el resultado!)

; Calcula fib(n-2)
mov eax, [ebp + 8]
sub eax, 2 ; n - 2
push eax
call fibonacci
add esp, 4
; eax = fib(n-2)

; eax = fib(n-1) + fib(n-2)
add eax, ebx ; eax = fib(n-2) + fib(n-1)

pop ebx ; Restaura ebx

fib_end:
pop ebp
ret

La versión recursiva de Fibonacci tiene una gran cantidad de cálculos repetidos. fib(10) llama a fib(9), fib(8), fib(8) se llama dos veces... lo que resulta en una complejidad temporal de O(2^n). En proyectos reales se recomienda usar la versión iterativa con bucles.

Versión iterativa de Fibonacci (comparación)

Ejemplo

; Ruta del archivo: fibonacci_iter.asm
; Versión iterativa: más eficiente, sin sobrecarga de recursión

section .data
n dd 10

section .text
global _start

_start:
mov ecx, [n] ; ecx = n
dec ecx ; Bucle n-1 veces (comenzando desde el segundo término)

mov eax, 0 ; fib(0) = 0
mov ebx, 1 ; fib(1) = 1

cmp ecx, 0
jle fib_done ; si n <= 1, retorna directamente

fib_loop:
mov edx, ebx ; Guarda el fib(n-1) anterior
add ebx, eax ; ebx = fib(n-1) + fib(n-2)
mov eax, edx ; Actualiza fib(n-2)
loop fib_loop

fib_done:
; Para n=10, al final ebx = 55
mov eax, 1
mov ebx, ebx ; Valor de retorno = fib(n)
int 0x80

Comparación entre recursión e iteración

Característica	Recursión	Iteración
Cantidad de código	Más corto, lógica clara	Más largo, pero buen rendimiento
Uso de pila	Cada llamada ocupa un marco de pila; si la profundidad es grande, puede desbordarse	Espacio fijo y pequeño
Rendimiento	Tiene sobrecarga de call/ret	Sin sobrecarga de llamada a función
Legibilidad	Intuitivo para problemas de inducción matemática	Requiere mantener manualmente el estado del bucle
Escenarios de uso	Recorrido de árboles, algoritmos de divide y vencerás, inducción matemática	Repetición simple, escenarios sensibles al rendimiento

En ensamblador, cada llamada recursiva consume espacio de pila. El tamaño de pila predeterminado en Linux es de aproximadamente 8 MB; una recursión con profundidad de 100000 puede provocar desbordamiento de pila. Para decidir cuándo usar recursión: cuando la profundidad de recursión del problema sea controlable (por ejemplo, profundidad de un árbol balanceado O(log n)) y la lógica recursiva sea mucho más clara que la iterativa.

Otras extensiones