Funciones Recursivas en C++: Guía de Reversing¶

Índice¶

Introducción
Parte 1: ¿Qué es la recursividad?
Parte 2: Ejemplo clásico - Factorial
Parte 3: Análisis del código fuente
Parte 4: Análisis a bajo nivel - Ensamblador
Parte 5: Trazado paso a paso - factorial(5)
Parte 6: Stack frames en recursividad
Parte 7: Consejos para reversing de funciones recursivas
Parte 8: Patrones comunes en ensamblador
Resumen

Introducción¶

Una función recursiva es aquella que se llama a sí misma. Es una técnica poderosa para resolver problemas que se pueden dividir en subproblemas más pequeños del mismo tipo. En reversing, reconocer recursividad es crucial porque:

El stack crece significativamente (múltiples frames)
Las operaciones se realizan "al retorno" (después de las llamadas recursivas)
Hay un punto de salida (condición base) que detiene la recursividad

Objetivo: Entender cómo aparecen las funciones recursivas en ensamblador, cómo trazar su ejecución, y reconocer patrones que indican recursividad.

Parte 1: ¿Qué es la recursividad?¶

Definición¶

Una función es recursiva si se llama a sí misma:

void recursiva() {
    recursiva();  // ¡Llamada a sí misma!
}

Componentes esenciales¶

Toda función recursiva necesita:

Componente	Descripción	Ejemplo
Caso base	Condición de salida (sin recursión)	`if (n == 1) return 1;`
Caso recursivo	Llamada a sí misma con parámetro modificado	`return n * factorial(n-1);`
Progreso hacia el caso base	El parámetro debe acercarse al caso base	`n-1` (decrementa hacia 1)

Sin caso base → Recursión infinita → Stack overflow

Ventajas y desventajas¶

Ventajas	Desventajas
✅ Código más limpio y legible	❌ Mayor uso de memoria (stack)
✅ Soluciones naturales para ciertos problemas	❌ Más lento que iteración (overhead de llamadas)
✅ Divide problemas complejos	❌ Puede causar stack overflow si no se controla

Parte 2: Ejemplo clásico - Factorial¶

Definición matemática¶

El factorial de un número $n$ (escrito $n!$) es:

$$n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1$$

Ejemplos: - $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ - $3! = 3 \times 2 \times 1 = 6$ - $1! = 1$ - $0! = 1$ (por definición)

Restricciones: - No se puede calcular el factorial de números negativos - El resultado crece muy rápido (limitado por el tamaño del tipo de dato)

Definición recursiva¶

El factorial se puede definir recursivamente:

$$ n! = \begin{cases} 1 & \text{si } n = 0 \text{ o } n = 1 \text{ (caso base)} \ n \times (n-1)! & \text{si } n > 1 \text{ (caso recursivo)} \end{cases} $$

Ejemplo: $5! = 5 \times 4!$, donde $4!$ se calcula recursivamente.

Parte 3: Análisis del código fuente¶

Código completo¶

#include <iostream>
using namespace std;

/* Función recursiva para cálculo de factoriales */
int factorial(int n) {
    if (n < 0) return 0;       // Error: factorial de negativo
    else if (n > 1) 
        return n * factorial(n - 1);  /* Recursividad */
    return 1;  /* Condición de terminación, n == 0 o n == 1 */
}

int main() {
    int resul = factorial(5);
    cout << "El factorial de 5 es: " << resul << endl;
    return 0;
}

Salida:

El factorial de 5 es: 120

Análisis de la lógica¶

Paso 1: Validación de entrada¶

if (n < 0) return 0;

Filtra números negativos (factorial no está definido)
Devuelve 0 como código de error

Paso 2: Caso recursivo¶

else if (n > 1) 
    return n * factorial(n - 1);

Si n > 1, llama a factorial(n-1)
Multiplica n por el resultado de la llamada recursiva
Importante: La multiplicación ocurre después del retorno de la llamada recursiva

Paso 3: Caso base¶

return 1;

Si n == 0 o n == 1, retorna 1
Este es el punto de salida de la recursión

Flujo de ejecución para `factorial(5)`¶

Llamadas (descendiendo):

main() → factorial(5)
         ├→ factorial(4)
            ├→ factorial(3)
               ├→ factorial(2)
                  ├→ factorial(1) → return 1

Retornos (ascendiendo, con multiplicaciones):

factorial(1) = 1
factorial(2) = 2 × factorial(1) = 2 × 1 = 2
factorial(3) = 3 × factorial(2) = 3 × 2 = 6
factorial(4) = 4 × factorial(3) = 4 × 6 = 24
factorial(5) = 5 × factorial(4) = 5 × 24 = 120

Nota crítica del video: Las operaciones (multiplicaciones) se realizan al retorno, no durante el descenso.

Parte 4: Análisis a bajo nivel - Ensamblador¶

Stack layout¶

Stack para factorial(5):

RSP+0x00: [Shadow Space (32 bytes)]
RSP+0x20: [Espacio para variables locales]
RSP+0x28: [Espacio adicional]
RSP+0x30: n$ (parámetro, 4 bytes)

Tamaño del frame: 40 bytes (0x28)

Código ensamblador completo (MSVC x64)¶

int factorial(int) PROC
$LN6:
        mov     DWORD PTR [rsp+8], ecx     ; Guardar parámetro n
        sub     rsp, 40                    ; Reservar stack frame

        ; Validación: n < 0?
        cmp     DWORD PTR n$[rsp], 0
        jge     SHORT $LN2@factorial       ; Si n >= 0, continuar
        xor     eax, eax                   ; return 0 (error)
        jmp     SHORT $LN1@factorial

$LN2@factorial:
        ; Caso base: n <= 1?
        cmp     DWORD PTR n$[rsp], 1
        jle     SHORT $LN4@factorial       ; Si n <= 1, return 1

        ; Caso recursivo: n > 1
        mov     eax, DWORD PTR n$[rsp]     ; EAX = n
        dec     eax                        ; EAX = n - 1
        mov     ecx, eax                   ; ECX = n - 1 (argumento)
        call    int factorial(int)         ; Llamada recursiva

        ; Multiplicación al retorno
        mov     ecx, DWORD PTR n$[rsp]     ; ECX = n
        imul    ecx, eax                   ; ECX = n * factorial(n-1)
        mov     eax, ecx                   ; EAX = resultado
        jmp     SHORT $LN1@factorial

$LN4@factorial:
        ; Caso base: return 1
        mov     eax, 1

$LN1@factorial:
        add     rsp, 40                    ; Limpiar stack
        ret     0
int factorial(int) ENDP

Análisis detallado por secciones¶

Sección 1: Prólogo y validación¶

mov     DWORD PTR [rsp+8], ecx     ; Guardar n en stack
sub     rsp, 40                    ; Reservar 40 bytes
cmp     DWORD PTR n$[rsp], 0
jge     SHORT $LN2@factorial
xor     eax, eax                   ; return 0 (n < 0)
jmp     SHORT $LN1@factorial

Explicación: 1. El parámetro n viene en ECX (convención x64) 2. Se guarda en [RSP+8] (shadow space) 3. Se reservan 40 bytes para el frame 4. Se compara n con 0 5. Si n < 0, retorna 0 (XOR rápido para poner 0 en EAX)

Sección 2: Caso base¶

$LN2@factorial:
        cmp     DWORD PTR n$[rsp], 1
        jle     SHORT $LN4@factorial
        ; ... (caso recursivo)

$LN4@factorial:
        mov     eax, 1                 ; return 1

Explicación: - Si n <= 1, salta a $LN4 y retorna 1 - Este es el punto de salida de la recursión

Sección 3: Caso recursivo (lo más importante)¶

; Preparar llamada recursiva
mov     eax, DWORD PTR n$[rsp]     ; EAX = n
dec     eax                        ; EAX = n - 1
mov     ecx, eax                   ; ECX = n - 1 (1er arg en x64)
call    int factorial(int)         ; Llamada recursiva

; Multiplicación al retorno
mov     ecx, DWORD PTR n$[rsp]     ; ECX = n (recargar desde stack)
imul    ecx, eax                   ; ECX = n * factorial(n-1)
mov     eax, ecx                   ; EAX = resultado final

Explicación paso a paso:

Preparar argumento:
mov eax, n: Cargar n actual
dec eax: Decrementar (n - 1)
mov ecx, eax: Pasar n-1 en ECX (convención x64)
Llamada recursiva:
call factorial: Llama a factorial(n-1)
El resultado viene en EAX
Multiplicación al retorno:
mov ecx, n$[rsp]: Recargar n desde el stack (porque EAX cambió)
imul ecx, eax: n * factorial(n-1)
mov eax, ecx: Resultado final en EAX para retornar

Nota crítica: El valor de n se recarga desde el stack después de la llamada recursiva, porque los registros pueden haber cambiado.

Parte 5: Trazado paso a paso - factorial(5)¶

Visualización del flujo¶

Nota del video: Para debugging de funciones recursivas, es recomendable anotar en papel (o programa de diagramas) el flujo de llamadas y valores de retorno.

MAIN
 └─> factorial(5)
      ├─ n=5, n>1 → Llama factorial(4)
      │   └─> factorial(4)
      │        ├─ n=4, n>1 → Llama factorial(3)
      │        │   └─> factorial(3)
      │        │        ├─ n=3, n>1 → Llama factorial(2)
      │        │        │   └─> factorial(2)
      │        │        │        ├─ n=2, n>1 → Llama factorial(1)
      │        │        │        │   └─> factorial(1)
      │        │        │        │        └─ n=1, caso base → return 1
      │        │        │        └─ return 2 * 1 = 2
      │        │        └─ return 3 * 2 = 6
      │        └─ return 4 * 6 = 24
      └─ return 5 * 24 = 120

Tabla de ejecución¶

Llamada	Valor de n	Acción	Valor de retorno	Multiplicación
`factorial(5)`	5	Llama `factorial(4)`	-	Pendiente
`factorial(4)`	4	Llama `factorial(3)`	-	Pendiente
`factorial(3)`	3	Llama `factorial(2)`	-	Pendiente
`factorial(2)`	2	Llama `factorial(1)`	-	Pendiente
`factorial(1)`	1	Caso base	1	-
`factorial(2)`	2	Recibe 1, multiplica	2	`2 × 1 = 2`
`factorial(3)`	3	Recibe 2, multiplica	6	`3 × 2 = 6`
`factorial(4)`	4	Recibe 6, multiplica	24	`4 × 6 = 24`
`factorial(5)`	5	Recibe 24, multiplica	120	`5 × 24 = 120`

Estados del stack¶

Durante el descenso (5 frames activos):

[Stack superior]
├─ Frame de factorial(1) ← RSP actual
├─ Frame de factorial(2)
├─ Frame de factorial(3)
├─ Frame de factorial(4)
├─ Frame de factorial(5)
└─ Frame de main
[Stack inferior]

Durante el ascenso (multiplicando):

[Stack superior]
├─ Frame de factorial(2) ← Multiplicando 2 × 1
├─ Frame de factorial(3)
├─ Frame de factorial(4)
├─ Frame de factorial(5)
└─ Frame de main
[Stack inferior]

Parte 6: Stack frames en recursividad¶

Contenido de cada frame¶

Cada llamada recursiva crea un stack frame independiente:

Frame de factorial(n):
+------------------+
| Return address   | (8 bytes)
| Shadow space     | (32 bytes)
| n$ (parámetro)   | (4 bytes en [RSP+48])
| Locals/padding   |
+------------------+

Ejemplo con factorial(5)¶

Estado del stack cuando está en factorial(1):

Dirección    Contenido                Frame
0x0010       Return to main           main
0x0018       ...                      main
0x0020       Return to factorial(5)   factorial(5)
0x0028       n=5                      factorial(5)
0x0048       Return to factorial(4)   factorial(4)
0x0050       n=4                      factorial(4)
0x0070       Return to factorial(3)   factorial(3)
0x0078       n=3                      factorial(3)
0x0098       Return to factorial(2)   factorial(2)
0x00A0       n=2                      factorial(2)
0x00C0       Return to factorial(1)   factorial(1)
0x00C8       n=1                      factorial(1) ← RSP

Tamaño total en stack para factorial(5):

5 frames × 40 bytes = 200 bytes
Más el frame de main

Nota del video: Para funciones con muchas recursiones (ej. factorial(100)), el stack puede crecer significativamente.

Parte 7: Consejos para reversing de funciones recursivas¶

1. Identificar patrones de recursividad¶

Indicios en ensamblador:

Una función que llama a sí misma (call a su propia dirección)
Decrementos o incrementos de parámetros antes de la llamada
Comparaciones con valores constantes (caso base)
Operaciones después del call (multiplicaciones, sumas, etc.)

Ejemplo:

mov     eax, DWORD PTR n$[rsp]
dec     eax
mov     ecx, eax
call    int factorial(int)      ; ← Llamada a sí misma
imul    ecx, eax                ; ← Operación al retorno

2. Anotar el flujo de ejecución¶

Método del video:

Usar papel y lápiz (o programa de diagramas como "hitm")
No dibujar el flujo del programa (grafo de control), sino el flujo de llamadas
Anotar valores:
Argumentos en cada llamada
Valores de retorno
Operaciones realizadas

Ejemplo de anotación:

main()
  └─> factorial(5)
       n=5, llama factorial(4)
       └─> factorial(4)
            n=4, llama factorial(3)
            └─> factorial(3)
                 n=3, llama factorial(2)
                 └─> factorial(2)
                      n=2, llama factorial(1)
                      └─> factorial(1)
                           n=1, return 1 ← Caso base
                      ← return 2 (2×1)
                 ← return 6 (3×2)
            ← return 24 (4×6)
       ← return 120 (5×24)

3. Usar debugger con breakpoints condicionales¶

Estrategia:

Poner breakpoint en el caso base (donde retorna sin recursión)
Poner breakpoint después del call (donde se hacen operaciones)
Usar breakpoints condicionales (ej. solo cuando n == 1)

En IDA Pro:

Breakpoint en 0x401234 (caso base)
Condición: [RSP+48] == 1

4. Verificar el stack¶

En x64dbg/IDA:

Ver el stack con Alt+K (stack view)
Buscar valores repetidos de direcciones de retorno (múltiples frames)
Verificar que los parámetros cambien entre frames

Parte 8: Patrones comunes en ensamblador¶

Patrón 1: Decremento y llamada¶

mov     eax, [rsp+n]
dec     eax              ; n - 1
mov     ecx, eax
call    funcion          ; Llamada recursiva con n-1

Indica: Recursión con decremento (común en factoriales, fibonacci, etc.)

Patrón 2: Comparación con constante¶

cmp     DWORD PTR [rsp+n], 1
jle     caso_base        ; Si n <= 1, salir

Indica: Condición de salida (caso base)

Patrón 3: Operación al retorno¶

call    funcion          ; Llamada recursiva
mov     ecx, [rsp+n]     ; Recargar parámetro
imul    ecx, eax         ; Multiplicar con resultado

Indica: Operación acumulativa al retornar

Patrón 4: Múltiples calls a la misma función¶

call    fibonacci        ; Primera llamada recursiva
mov     [rsp+temp], eax  ; Guardar resultado
call    fibonacci        ; Segunda llamada recursiva
add     eax, [rsp+temp]  ; Sumar resultados

Indica: Recursión múltiple (ej. Fibonacci con 2 llamadas)

Resumen¶

Conceptos clave¶

Recursividad: Función que se llama a sí misma
Caso base: Condición de salida (sin recursión)
Caso recursivo: Llamada con parámetro modificado
Operaciones al retorno: Se ejecutan después de las llamadas recursivas

Factorial en pocas palabras¶

$$ \text{factorial}(n) = \begin{cases} 0 & \text{si } n < 0 \text{ (error)} \ 1 & \text{si } n \leq 1 \text{ (caso base)} \ n \times \text{factorial}(n-1) & \text{si } n > 1 \text{ (recursivo)} \end{cases} $$

En ensamblador¶

Múltiples frames en stack (uno por cada llamada)
Parámetros se recargan después del call (pueden cambiar)
Patrón típico: dec + call + operación con imul/add
Caso base: cmp + salto directo a return

Consejos de reversing¶

Técnica	Cuándo usar
Anotar en papel	Recursiones largas o complejas
Breakpoint en caso base	Para ver el punto de salida
Breakpoint después de call	Para ver operaciones al retorno
Stack view	Para contar frames activos

Limitaciones¶

Stack overflow: Si no hay caso base o no se alcanza
Rendimiento: Más lento que iteración (overhead de llamadas)
Memoria: Crece linealmente con la profundidad de recursión