El pastel de Piper

Recursión

Una función es recursiva cuando se llama a sí misma.

Una diferencia clave entre una llamada a función y un bucle es que llamar a una función coloca en la pila la dirección de retorno. Esto significa que una función recursiva normalmente necesita más espacio en la pila que un bucle equivalente.

Como consecuencia, una función que no deja de llamarse a sí misma puede llegar a agotar todo el espacio de la pila. A esto se le llama desbordamiento de pila.

Por eso toda función recursiva debe tener al menos un caso base, que es una situación en la que la función devuelve un valor sin llamarse a sí misma. Toda llamada recursiva debe llegar tarde o temprano a un caso base.

Por ejemplo, la función factorial n! = n * (n - 1) * ... * 1 se puede definir de forma recursiva con 1 como caso base:

factorial:
    ; the argument `n` is passed on `rdi`
    ; the factorial will be returned on `rax`

    cmp rdi, 1
    jle .base_case     ; base case -> if rdi <= 1, return 1

    push rdi           ; save n
    dec rdi            ; rdi = n - 1
    call factorial     ; recursive call, rax = (n - 1)!
    pop rdi            ; restore n
    imul rax, rdi      ; rax = n * (n - 1)! = n!
    ret
.base_case:
    mov rax, 1
    ret

Fíjate que factorial debe hacer push rdi antes de la llamada recursiva y pop rdi después. Esto es porque todavía necesita n una vez que la llamada recursiva finaliza, para calcular n * (n-1)!.

Fíjate además que usar un registro preservado por la función llamada no resolvería este problema.

Aunque una función recursiva puede llamarse a sí misma, también es la función llamada por parte de otra función. Eso significa que la función también debe preservar los registros que le corresponde conservar como función llamada antes de usarlos, y restaurar su valor cuando termina de usarlos. Esto normalmente se hace con una secuencia de push/pop, como vimos en un concepto anterior.

Como cada marco de una función recursiva, con la excepción del caso base, también es quien llama y necesita preservar sus propias variables locales, esta secuencia de push/pop debe repetirse para cada marco. Incluso guardar la variable directamente en la pila, sin usar registros, seguiría costando los mismos 8 bytes por marco.

Esto significa que cada llamada recursiva añade 8 bytes a la pila por la dirección de retorno que coloca call, más 8 bytes por cada variable local que necesita guardar. La función seguirá añadiendo esos bytes a la pila en cada marco hasta que llegue a su caso base. Solo entonces empieza a desenrollarse en orden inverso, y cada llamada recursiva usa tantos pop como necesite y luego un ret.

Por ejemplo, si se llamara a factorial con el argumento 10, se llamaría a sí misma nueve veces antes de llegar al caso base de 1. En ese punto, se habrían usado 144 bytes para guardar la n (8 bytes) y la dirección de retorno (8 bytes) de cada marco anterior.

Llamada de cola

En algunas situaciones, una función no realiza más trabajo después de llamar a otra y antes de retornar.

Considera, por ejemplo:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    call times_three
    ret

La función triple_of_square:

• multiplica por sí mismo el argumento que recibe (en rdi), obteniendo su cuadrado;
• luego llama a times_three, que devuelve tres multiplicado por el argumento que se le pasa.

Como resultado, triple_of_square devuelve 3*x², donde x es su argumento, que se pasa en rdi.

Fíjate que en triple_of_square no se hace ningún trabajo después de llamar a times_three: la función simplemente retorna. En una situación como esta, en lugar de usar call, una función puede usar jmp y transferir la ejecución a la función llamada:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    jmp times_three

A esto se le llama llamada de cola.

La principal ventaja de una llamada de cola es que evita el costo extra de call. Un call coloca una dirección de retorno en la pila, y para que el control vuelva a ese punto debe haber un ret que le corresponda.

Una llamada de cola se salta ambas cosas: no hay dirección de retorno que colocar ni un ret adicional con el que emparejar, solo el ret propio de la función llamada.

Recursión de cola

Una llamada de cola es especialmente útil para funciones recursivas que pueden llamarse a sí mismas muchas veces antes de retornar.

Sin embargo, no toda llamada recursiva se puede convertir directamente en una llamada de cola. Como un jmp transfiere el control a la función llamada, quien llama ya no puede realizar más trabajo después de la llamada de cola.

Por ejemplo, la función factorial que vimos antes no es recursiva de cola. Después de la llamada recursiva, todavía necesita multiplicar el resultado por la n actual, usando imul rax, rdi.

En situaciones como esta, a veces es posible usar un acumulador que vaya recogiendo los cálculos parciales y se devuelva al final. Por ejemplo, podemos definir un factorial_helper que haga la mayor parte del trabajo, y luego factorial prepara un acumulador y transfiere el control a factorial_helper:

factorial_helper:
    ; the argument `n` is passed on `rdi`
    ; `rax` is used as an accumulator and will be returned at the end

    cmp rdi, 1
    jle .base_case

    imul rax, rdi        ; we accumulate the partial result on `rax`
    dec rdi              ; rdi = n - 1
    jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
    ret                  ; returns the factorial already accumulated on `rax`

factorial:
    mov rax, 1           ; initial value for the accumulator
    jmp factorial_helper ; tail call

Como ya no se hace más trabajo después de la llamada recursiva, tampoco necesitamos guardar rdi. No hay ningún call ni push rdi, así que cada iteración recursiva añade 0 bytes a la pila: no se usa espacio adicional en la pila. Esta versión puede manejar valores de n arbitrariamente grandes sin desbordar la pila. Es a la vez más eficiente y más segura.

En algunos casos, manipulando el orden de las funciones, se puede evitar incluso el jmp hacia la función auxiliar. Por ejemplo, factorial y triple_of_square se pueden reescribir de esta manera:

factorial:
    mov rax, 1
factorial_helper:
    cmp rdi, 1
    jle .base_case

    imul rax, rdi
    dec rdi
    jmp factorial_helper
.base_case:
    ret

triple_of_square:
    imul rdi, rdi
times_three:
    imul rax, rdi, 3
    ret

En el fragmento anterior, la ejecución de factorial continúa directamente en factorial_helper. Lo mismo ocurre con triple_of_square y times_three. En ambos casos, la ejecución continúa de forma secuencial y parece que la función de cola es solo una etiqueta local dentro de la función «main».

En realidad, no hay ninguna diferencia esencial entre cualquier etiqueta local y una función. El ensamblador de x86-64 no les da ningún trato especial a ninguna de ellas: solo son direcciones en una sección con código ejecutable, como section .text.

De esta forma, una función recursiva de cola se puede pensar esencialmente igual que un bucle en el que la llamada recursiva salta de vuelta al inicio y el caso base es la condición que termina el bucle.