Recursão de cauda — ou como não estourar a pilha

Quando precisamos realizar uma operação várias vezes, geralmente existem duas maneiras: iterativa e recursiva. Iterativa é quando utilizamos alguma estrutura de laço, como um for ou while, com uma variável de controle para saber quando parar. Recursiva é quando uma função decide executar a si mesma por entender que ainda precisa continuar processando. Toda iteração pode ser escrita como uma recursão e vice-versa. Recursões porém tem um risco associado: o estouro da pilha. Vamos entender o que isso significa e como escrever código recursivo evitando esse problema!

O que é essa pilha?

Antes de mais nada, o que é a pilha? Neste contexto, não estamos falando de uma bateria 🔋, mas de uma estrutura de dados em que podemos empilhar informação 🥞. Sempre que executamos uma função, nós estamos movendo a execução do código de um ponto para o outro. Quando a função que chamamos termina, precisamos voltar para onde estávamos com o resultado e continuar a execução. Por isso, quando chamamos uma função, o ambiente de execução vai guardar o estado atual de execução em algum lugar para que possamos retornar para ele depois. Diferentes linguagens de programação vão ter diferentes ambientes de execução, mas o conceito é parecido entre elas.

Cada chamada de função adiciona esse contexto numa pilha (em inglês, stack). Usa-se uma pilha pois, se nós executamos a função A, que chama a função B, que chama C (nessa ordem), ao final de C nós queremos retornar para B e, ao final de B, nós queremos retornar para A. Assim, vamos empilhando as chamadas aninhadas (chamadas dentro de chamadas) e desempilhando nos retornos. Cada contexto desse adicionado na pilha é chamado de quadro (stack frame) e ocupa espaço em memória.

Memória não é infinita, e cada ambiente de execução de código vai definir um limite para o quão profunda uma pilha de chamadas de função pode ser. Se esse tamanho for, por exemplo, 1000, significa que você pode ter no máximo 1000 níveis de funções chamando umas as outras sem retornar, de acordo com o que a função precisar guardar na pilha. Se você tentar chamar mais uma função aninhada, você vai ter um estouro da pilha, de onde vem o nome do Stack Overflow.

O que isso tem a ver com recursão?

É difícil imaginar escrever 1000 funções de maneira que uma chame a outra, consequentemente ultrapassando esse limite. Afinal de contas, você vai ter o limite da própria quantidade de código que você escreve. Porém, existe algo bem mais rápido e capaz do que nós, humanos: computadores. E aí que entra recursão.

Imagine o seguinte cenário, em JavaScript. Note que estou colocando um n ao final dos números. Essa é a sintaxe para BigInt em JS, que são números arbitrariamente grandes. O exemplo a seguir faz conta com número muito grandes e, se usarmos números padrões de JavaScript, chegaríamos em Infinity eventualmente.

function factorial(number) {
  if (number === 0n) {
    return 1n
  } else {
    return number * factorial(number - 1n)
  }
}

Temos uma função recursiva que calcula o fatorial de um número (o produto de todos os números entre 1 e este número). Ela é recursiva pois tem um caso base (se number for igual a zero) em que ela apenas retorna algo e um caso recursivo (se number não for igual a zero), em que ela faz algo e chama a si mesma com outro argumento.

factorial(10n) // Resultado: 3628800n

Essa função vai precisar usar a pilha number vezes, pois cada execução dela precisa chamar uma função (ela mesma) antes de poder retornar. Ou seja, quando eu chamo factorial(10), essa função retornar 10 * factorial(9). Mas ela não consegue retornar ainda, pois tem uma chamada de função não resolvida. Ela precisa esperar factorial(9) retornar para depois poder multiplicar por 10, e assim retornar também. Isso acontece sucessivamente até chegar em factorial(0), que retorna apenas 1. A partir daí, os contextos de execução das funções vão sendo desempilhados, passando pelo factorial(1) (que aguardava o resultado do factorial(0)), depois factorial(2), e assim até voltar para o original, factorial(10).

Se a entrada dessa função se tornar muito grande, vamos precisar fazer um número de chamadas de função, uma dentro da outra, que pode precisar guardar mais informação na pilha do que ela suporta, causando um estouro da pilha. Nos meus testes, rodando em Node.js, factorial(10948n) foi o ponto em que a pilha estouraria. Ao tentar executar essa função, eu recebi a mensagem: Uncaught RangeError: Maximum call stack size exceeded.

O motivo de precisarmos guardar informação na pilha de chamadas de função é que essa função precisa fazer algo com o resultado da chamada recursiva. Mais especificamente, olhando para essa linha dentro do else:

    return number * factorial(number - 1n)

A função precisa que a chamada recursiva retorne para depois conseguir fazer a multiplicação. Para visualizar, vamos diminuir a entrada para 5n. A execução aconteceria, passo a passo, assim:

factorial(5n)
5n * factorial(4n)
5n * 4n * factorial(3n)
5n * 4n * 3n * factorial(2n)
5n * 4n * 3n * 2n * factorial(1n)
5n * 4n * 3n * 2n * 1n * factorial(0n)
5n * 4n * 3n * 2n * 1n * 1n // Chegamos no caso base
5n * 4n * 3n * 2n * 1n
5n * 4n * 3n * 2n
5n * 4n * 6n
5n * 24n
120n

É aí que entra o conceito de recursão de cauda, ou otimização de chamada de cauda (tail call optimization).

Como fazer essa recursão não estourar?

Algumas linguagens de programação conseguem identificar chamadas de funções que não precisam guardar contexto na pilha. Quando isso acontece, é possível ter uma recursão que, independentemente da profundidade, não vai causar um estouro da pilha.

Infelizmente, JavaScript não é uma delas. As implementações atuais não suportam esse tipo de otimização. Para fins ilustrativos, vamos rever como seria o exemplo acima se JavaScript tivesse suporte a recursão de cauda. Depois, vamos ver o mesmo exemplo em linguagens que de fato suportam.

Vamos re-escrever a função do fatorial de maneira que ela não precise esperar pelo retorno da recursão para retornar. O segredo está em fazer com que, em todos os possíveis caminhos para o código, nós retornemos apenas valores ou a própria chamada recursiva.

function factorial(number, product) {
  if (number === 0n) {
    return product
  } else {
    return factorial(number - 1n, product * number)
  }
}

A função acima tem dois caminhos possíveis de execução. O primeiro caminho, se number for zero, retorna apenas um valor (a variável product). O segundo, se number não for zero, é o que modificamos. Ao invés de retornar o valor atual multiplicado pelo retorno da recursão, nós calculamos a multiplicação primeiro e só depois fazemos a chamada recursiva.

Para isso, introduzimos um segundo argumento a essa função, o product. Ele funciona aqui como um acumulador, que guarda o resultado intermediário. Esse acumulador vai guardando cada multiplicação e é retornado no caso base, quando chegamos no fim da recursão. Como nós passamos esse resultado intermediário na chamada recursiva, nosso return não faz nada com o resultado da recursão, apenas retorna-o diretamente. O interpretador do JavaScript poderia perceber isso e não guardar nada na pilha.

Vamos ver como ficaria a sequência de execução dessa nova função. Note que, como ela tem um acumulador (segundo parâmetro), precisamos passar algum valor inicial para esse parâmetro. Como é uma multiplicação, podemos passar 1n (pois 1 não afeta um produto).

factorial(5n, 1n)
factorial(4n, 5n)
factorial(3n, 20n)
factorial(2n, 60n)
factorial(1n, 120n)
factorial(0n, 120n)
120n

Sobre esse segundo argumento, idealmente não gostaríamos que fosse necessário passá-lo para começar a calcular. Para isso, podemos separar a implementação da função da API pública, assim:

function factorialImplementation(number, product) {
  if (number === 0n) {
    return product
  } else {
    return factorialImplementation(number - 1n, product * number)
  }
}

// A função que exportamos publicamente apenas tem um argumento
export function factorial(number) {
  return factorialImplementation(number, 1n)
}

Assim, nossa função factorial só recebe um argumento. Alternativamente, poderíamos colocar um valor padrão para o segundo argumento (mas isso permitiria chamar a função passando um segundo argumento errado, ainda assim).

Exemplos em linguagens que suportam otimização de chamadas de cauda

Como eu comentei, infelizmente JavaScript não tem suporte a não adicionar contexto na pilha caso não seja necessário. Toda chamada de função vai colocar algo na pilha e, eventualmente, uma recursão causa um estouro.

Vamos rever o exemplo do fatorial em algumas linguagens que têm suporte a essa otimização.

Clojure

(defn factorial
  "Implementação sem tail call optimization"
  [number]
  (if (zero? number)
    1
    (* number (factorial (dec number)))))

(defn factorial
  "Implementação com tail call optimization"
  [number product]
  (if (zero? number)
    product
    (recur (dec number) (* product number))))

Note que, em Clojure, existe uma forma especial para recursão de cauda: recur. Usamos recur no lugar do nome da função, para executar uma chamada recursiva. Se você tentar usar recur num contexto que ele não seja a última execução de um caminho da execução de código, vai receber um erro. Se você tentar escrever recursões sempre com recur, você tem a garantia de fazer uma recursão de cauda (pois o compilador não vai deixar você não o fazer).

Kotlin

// Implementação sem tail call optimization
fun factorial(number: Long) : Long {
    return if (number === 0) {
        1
    } else {
        number * factorial(number - 1)
    }
}

// Implementação com tail call optimization
tailrec fun factorial(number: Long, product: Long) : Long {
    return if (number === 0) {
        product
    } else {
        factorial(number - 1, product * number)
    }
}

Kotlin possui a palavra-chave tailrec. Se aplicada a uma função, indica que a recursão dessa função é de cauda. Se você aplicar esse modificador na primeira versão, por exemplo, terá um erro, assim como o uso do recur em Clojure.

Haskell

-- Implementação sem tail call optimization
factorial :: (Integral a) => a -> a
fatorial 0 = 1
factorial n = n * factorial (n - 1)

-- Implementação com tail call optimization
factorial :: (Integral a) => a -> a -> a
fatorial 0 p = p
factorial n p = factorial (n - 1) (p * n)

Elixir

Recentemente, eu escrevi um post sobre casamento de padrões com Elixir. No final dele tem esse exemplo de fatorial usando casamento de padrões e recursão de cauda. Ela também deixa pública apenas a chamada da função com um argumento, mantendo a versão com o acumulador privada.

defmodule Math do
  def factorial(number) do
    factorial(number, 1)
  end

  defp factorial(0, current_product) do
    current_product
  end

  defp factorial(number, current_product) do
    factorial(number - 1, number * current_product)
  end
end

Eu posso usar recursão de cauda na minha linguagem favorita?

Depende de qual é ela.

Não coincidentemente, os três exemplos de linguagens que suportam otimização de chamada de cauda que eu trouxe são linguagens funcionais. Normalmente, programação funcional utiliza recursão com uma frequência superior a iteração, e linguagens funcionais têm essa preocupação com performance e limitações de memória.

A Wikipédia tem uma lista com algumas linguagens que suportam essa otimização. Você vai ver que, em maioria, são linguagens funcionais. Se essa maneira de pensar te interessou, e você nunca aprendeu uma linguagem funcional, que tal experimentar? Se aceita uma sugestão, dá uma olhada em Clojure ou Elixir!