La tarta 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 empuja a la pila la dirección a la que hay que volver. Esto significa que una función recursiva normalmente necesita más espacio de pila que un bucle equivalente.

Como consecuencia, una función que se llama a sí misma una y otra vez puede acabar agotando todo el espacio de pila. Esto se conoce como desbordamiento de pila.

Por eso toda función recursiva debe tener al menos un caso base, es decir, una situación en la que la función devuelve un valor sin llamarse a sí misma. Cualquier llamada recursiva debe acabar alcanzando 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 en que factorial debe hacer push rdi antes de recursar y pop rdi después. Esto se debe a que todavía necesita n cuando la llamada recursiva devuelve el control, para poder calcular n * (n-1)!.

Fíjate también en que usar un registro que la función llamada deba conservar no resolvería este problema.

Aunque una función recursiva puede llegar a llamarse a sí misma, también es la función llamada por otra función. Eso significa que la función también debe conservar los registros que, como función llamada, debe guardar antes de usarlos, y restaurar su valor después de usarlos. Normalmente esto se hace con una secuencia de push/pop, como vimos en un concepto anterior.

Como cada marco de una función recursiva, salvo el del caso base, también es un llamador que necesita preservar sus propias variables locales, esta secuencia de push/pop debe repetirse en cada marco. Incluso guardando 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 empuja call, más 8 bytes por cada variable local que necesite guardar. La función seguirá añadiendo esos bytes a la pila en cada marco hasta que alcance su caso base. Solo entonces empieza a desenrollarse en orden inverso, y cada llamada recursiva usa tantos pop como necesite y después un ret.

Por ejemplo, si se llamara a factorial con el argumento 10, se llamaría a sí misma nueve veces antes de alcanzar el caso base de 1. En ese momento 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 devolver el control.

Fíjate, por ejemplo, en este caso:

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;
• después llama a times_three, que devuelve el triple del 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 en que en triple_of_square no se hace ningún trabajo después de llamar a times_three: la función simplemente devuelve el control. En una situación así, 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

Esto se conoce como llamada de cola.

La principal ventaja de una llamada de cola es que evita el coste adicional de call. Un call empuja una dirección de retorno a la pila y, para que el control vuelva a ese punto, debe haber un ret correspondiente.

Una llamada de cola se salta ambas cosas: no hay dirección de retorno que empujar ni un ret adicional con el que emparejarla, solo el ret de la propia 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 devolver el control.

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 no puede realizar más trabajo después de la llamada de cola.

Por ejemplo, la función factorial anterior 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 así, 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 después factorial prepara un acumulador y le 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 ningún push rdi, así que cada iteración recursiva añade 0 bytes a la pila: no se usa espacio de pila adicional. 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 a la función auxiliar. Por ejemplo, factorial y triple_of_square se pueden reescribir así:

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 no es más que una etiqueta local dentro de la función «principal».

En realidad, no hay ninguna diferencia esencial entre una etiqueta local cualquiera y una función. El ensamblador de x86-64 no da un trato especial a ninguno de los dos: no son más que direcciones en una sección con código ejecutable, como section .text.

De este modo, una función recursiva de cola se puede concebir esencialmente igual que un bucle en el que la llamada recursiva salta de vuelta al principio y el caso base es la condición que pone fin al bucle.