Recursão: Programação Funcional

Por que linguagem funcional vive de recursão

Antes da recursão de cauda vem uma pergunta mais básica: por que linguagem funcional depende tanto de recursão? A resposta cabe em uma palavra, imutabilidade.

Numa linguagem mutável, x = 1 escreve o valor 1 num endereço de memória e x = 2 volta no mesmo endereço e sobrescreve. Numa linguagem imutável, o segundo comando escreve o 2 em outro endereço, e o 1 continua lá até o garbage collector perceber que ninguém mais aponta para ele. Nada é alterado: tudo o que parece alteração é uma cópia nova.

Há um jeito de ver isso que ninguém esquece. Em Elixir, se você cria uma função anônima que imprime x quando x vale 2, depois reatribui x = 4 e chama a função de novo, ela ainda imprime 2: a função ficou apontando para o endereço antigo, que nunca mudou.

A consequência prática é o que interessa aqui. Este laço, que é o pão com manteiga de qualquer linguagem imperativa, simplesmente não existe no mundo funcional:

for i in range(len(nums)):
    nums[i] = nums[i] * 2      # escreve por cima: proibido

Para fazer isso preservando a imutabilidade, cada iteração teria que copiar o array inteiro e só então gravar a posição alterada. Com 1.000 elementos, seriam 1.000 cópias de 1.000 posições: 1 milhão de escritas para dobrar 1.000 números, um O(n²) gratuito. Inviável.

Se a estrutura é head mais tail, percorrer vira recursão sem esforço: faça algo com o head, chame de novo com o tail, pare quando a lista estiver vazia. Em Elixir o caso base nem entra na função: ele vira outra cláusula da mesma função, escolhida por pattern matching.

def dobrar([]), do: []
def dobrar([head | tail]), do: [head * 2 | dobrar(tail)]

E não adianta fugir para os módulos prontos. Abra o código-fonte do Enum.map do Elixir, que chama o lists:map do Erlang, e lá dentro está exatamente a mesma coisa: um caso para lista vazia, um caso para [head | tail], e uma chamada recursiva. O for do Elixir (que é uma list comprehension, não um laço) desce no mesmo lugar. Não tem mágica: o açúcar sintático existe para você não reescrever isso toda vez, mas embaixo é sempre recursão.

O que nos traz ao problema. Se toda travessia é recursão, uma lista de 1 milhão de elementos vira 1 milhão de chamadas empilhadas. A saída não está em evitar a recursão, está na forma de escrever a chamada.

A pilha que cresce e a conta que espera

O exemplo canônico é somar os números de uma lista:

def soma(nums):
    if not nums:
        return 0
    return nums[0] + soma(nums[1:])

Rode na cabeça com [1, 2, 3, 4]. Na ida, nenhuma soma acontece. A primeira chamada precisa do resultado de soma([2, 3, 4]) para poder somar 1, então ela guarda o 1 + pendurado e desce. A segunda faz o mesmo com o 2 +. Quando a lista finalmente esvazia, a pilha tem 5 frames vivos (4 chamadas mais o caso base) e nem uma conta foi feita.

Só aí a volta começa, e aí sim as contas saem, uma por frame desempilhado:

soma([])            -> 0
soma([4])           -> 4 + 0 = 4
soma([3, 4])        -> 3 + 4 = 7
soma([2, 3, 4])     -> 2 + 7 = 9
soma([1, 2, 3, 4])  -> 1 + 9 = 10

Um desenho explica melhor que qualquer parágrafo: cada chamada é uma caixa dentro da anterior. Enquanto a mais interna não termina, todas as de fora continuam vivas, com o escopo delas inteiro na memória, esperando um valor que ainda não existe.

Isso custa dos dois lados: se empilhar custa 1 e desempilhar custa 1, uma recursão sobre 10 elementos custa 20. Se desse para não empilhar, custaria 10.

Repare que o número de somas não muda: é uma por elemento, na volta em vez da ida. O que essa forma cobra é espaço: O(n) de pilha, um frame por elemento, só porque cada frame ficou com uma conta pendurada esperando.

Posição de cauda: a regra de uma linha só

Uma chamada está em posição de cauda quando ela é a última coisa que a função faz: o valor que ela devolver é, sem passar por mais nada, o valor que a função devolve.

O teste é olhar o return e perguntar: sobrou alguma conta pendurada na chamada?

return nums[0] + soma(resto)        # sobrou: o "+" ainda tem que acontecer
return soma(resto, acc + nums[0])   # não sobrou: a conta já aconteceu no argumento

A diferença parece cosmética e não é. Na primeira linha, a soma acontece depois que a chamada volta, então o frame tem que sobreviver. Na segunda, acc + nums[0] é avaliado antes, para montar o argumento; quando a chamada acontece, o frame atual já não tem mais nada a fazer no mundo.

Vale separar dois termos com cuidado, porque eles são confundidos o tempo todo:

• Tail call (chamada de cauda): a última instrução da função é chamar outra função.
• Tail recursion (recursão de cauda): a última instrução é chamar ela mesma.

A pergunta natural aqui é se a otimização vale para os dois casos, e a resposta é sim: o que ela usa não é o fato de ser recursiva, é o fato de não sobrar nada para fazer no frame atual.

Passeie pelos sete casos do classificador abaixo antes de seguir:

Compare o caso 1 com o caso 2: é a mesma função, o mesmo resultado, e o veredito muda por causa de onde a soma está escrita. O caso 4 é a distinção de nomes na tela: a última instrução chama outra função, não a si mesma, e o selo verde continua lá. Olhe o caso 5, o fibonacci ingênuo: nem a primeira nem a segunda chamada estão em posição de cauda, porque fib(n - 1) tem que voltar para o + acontecer. E repare no caso 6: um if antes não atrapalha nada, o que conta é a última instrução executada em cada caminho. Guarde o caso 7, ele volta no fim da página como o contraexemplo mais interessante do assunto.

O acumulador: fazer a conta na ida

A receita para transformar recursão comum em recursão de cauda é sempre a mesma: um parâmetro a mais, o acumulador, carregando o resultado parcial. A conta que estava na volta passa para a ida.

def soma(nums, acc=0):
    if not nums:
        return acc              # o resultado já está pronto na mão
    return soma(nums[1:], acc + nums[0])

Com [1, 2, 3, 4], o acumulador faz este caminho: 0, 1, 3, 6, 10. Quando a lista esvazia, não existe volta para calcular: a resposta já é o acc. Compare com a versão comum, que só começa a somar depois de empilhar tudo, e faz 4 + 0, 3 + 4, 2 + 7, 1 + 9.

A receita em quatro passos

Essa transformação não é inspiração, é mecânica. Sempre que você tiver uma recursão comum na mão, faça isto:

1. Olhe o que sobrou pendurado no return. Na soma é o nums[0] +. Essa é a conta que hoje acontece na volta.
2. Crie um parâmetro novo com o elemento neutro dessa conta. Neutro é o valor que não muda o resultado: 0 para a soma, 1 para o produto, [] para a lista.
3. Mova a conta para dentro do argumento. O que era nums[0] + soma(resto) vira soma(resto, acc + nums[0]). É a única mudança de verdade, e é ela que esvazia o frame.
4. O caso base devolve o acumulador, não o neutro. return acc, nunca mais return 0.

O passo 2 é o que mais dá errado, porque o neutro muda com a operação:

O visualizador abaixo roda as duas formas lado a lado, sobre a mesma lista:

Rode passo a passo e olhe só para o número de frames. À esquerda a pilha sobe até 5 e depois desce, fazendo uma conta por frame. À direita ela fica em 1, porque o frame é reescrito no lugar, e o rastro do acumulador embaixo mostra a resposta sendo construída na descida.

Agora olhe os dois contadores de soma no painel de variáveis. somas · comum fica travado em 0 de 4 durante a descida inteira e só começa a andar na volta; somas · cauda chega a 4 de 4 antes da volta sequer existir. No fim, os dois marcam 4. É a prova na tela de que a recursão de cauda não faz menos contas: ela só faz as mesmas contas mais cedo, e é por isso que o frame pode ser jogado fora.

Agora faça o experimento que fecha a ideia: clique em "Python, Java, C# (sem TCO)" e rode de novo. Os dois lados voltam a empilhar 5 frames. Este é o ponto mais importante da página:

Agora troque de preset e preveja antes de rodar: com a lista vazia, qual é o pico de frames de cada lado? E com um elemento só? (O visualizador responde: 1 e 1 na lista vazia, 2 contra 1 com um elemento.)

A mesma receita transforma o fibonacci, e aqui ela muda mais que a memória:

def fib(n, a=0, b=1):
    if n == 0:
        return a
    return fib(n - 1, b, a + b)   # em posição de cauda

As duas devolvem 832.040 para fib(30), mas a versão ingênua faz 2.692.537 chamadas para chegar lá e a de cauda faz 31. O tempo caiu de O(2ⁿ) para O(n), porque o acumulador carrega o que a versão ingênua recalculava sem parar.

Repare no que aconteceu com a direção do raciocínio. A recursão comum é top-down: quebre o problema, resolva os pedaços, junte na volta. A de cauda é bottom-up: resolva o pedaço agora, empurre o resultado para frente, e no fim ele já está pronto. É exatamente a virada que reaparece em Programação Dinâmica, e não é coincidência que a versão bottom-up quase sempre pareça menos intuitiva na primeira leitura.

A conta troca de lado, e isso muda o resultado

Mover a operação para a ida não é neutro. Com uma operação associativa e comutativa como a soma, tanto faz: 1 + (2 + 3) e (1 + 2) + 3 dão 6. Com uma operação que não é, o resultado muda de verdade. Subtraia os elementos de [10, 3, 2] das duas formas:

def sub_comum(nums):                    # 10 - (3 - (2 - 0)) = 9
    if not nums:
        return 0
    return nums[0] - sub_comum(nums[1:])

def sub_cauda(nums, acc=0):             # ((0 - 10) - 3) - 2 = -15
    if not nums:
        return acc
    return sub_cauda(nums[1:], acc - nums[0])

Nove contra menos quinze, com a mesma lista. A recursão comum associa da direita para a esquerda e a de cauda da esquerda para a direita. Se você já viu foldr e foldl em Haskell, ou Enum.reduce em Elixir, é exatamente esta distinção: a recursão comum é um foldr, a de cauda é um foldl. Antes de converter, pergunte se a sua operação aguenta a troca de lado. Soma, produto, contagem, máximo e "existe algum" aguentam. Subtração, divisão, concatenação e construção de lista não.

O acumulador não precisa ser um número

E aqui está a parte mais bonita do assunto: dá para validar parênteses em Elixir sem escrever um único if. O acumulador é uma pilha, e cada cláusula da função trata um caso.

def valido?(texto), do: validar(String.graphemes(texto), [])

defp validar([], []),                    do: true    # texto acabou e a pilha esvaziou
defp validar([], _pilha),                do: false   # sobrou parêntese aberto
defp validar(["(" | resto], pilha),      do: validar(resto, [")" | pilha])
defp validar([")" | resto], [")" | p]),  do: validar(resto, p)
defp validar([")" | _resto], _pilha),    do: false   # fechou o que não abriu
defp validar([_ | resto], pilha),        do: validar(resto, pilha)

Leia de cima para baixo, que é a ordem em que o Elixir tenta casar: os dois casos base primeiro, depois "abri um parêntese" (empilho o fechamento que estou devendo), depois "fechei o que devia" (desempilho), depois "fechei o que não abriu", e por último "é outro caractere qualquer, sigo em frente". As seis cláusulas de validar terminam em uma chamada ou em um valor, nenhuma tem conta pendurada: é recursão de cauda do começo ao fim, e roda em O(1) de pilha na BEAM.

Guarde o formato, porque ele é a solução do Valid Parentheses do LeetCode, e é a mesma ideia de Pilhas vista pelo outro lado: onde a linguagem imperativa usa um stack.push(), a funcional passa a pilha adiante no argumento.

Tail call optimization: quem otimiza e quem não

Tail call optimization (TCO) é o que o compilador faz quando enxerga uma chamada em posição de cauda: em vez de empilhar um frame novo, ele reaproveita o frame atual, trocando só os parâmetros. Na prática, é quase um goto para o começo da própria função.

Vale ajustar um detalhe do modelo mental mais comum: não é que o frame anterior seja ignorado, é que ele é substituído. Como ninguém precisa mais dele (não sobrou conta nenhuma para fazer ali), a linguagem pode escrever a chamada nova por cima.

O efeito é o que a gente viu: a complexidade de espaço cai de O(n) para O(1), e a recursão deixa de ter teto. Uma lista de 1 milhão de elementos passa sem stack overflow, porque o número de frames nunca muda.

O caso do Python é o mais instrutivo, porque a ausência é de propósito. O Guido escreveu sobre isso: a otimização apagaria frames do stack trace, deixando depuração pior, e recursão nunca foi o idioma da linguagem. A recomendação oficial continua sendo escrever o laço.

Por isso o botão do visualizador da seção anterior importa tanto. Em Elixir a função de cauda que você escreveu é um laço depois de compilada. Em Python, ela é a mesma recursão de antes, só que com um parâmetro a mais.

Sem TCO, você faz a conversão na mão

A boa notícia é que, uma vez que a função está em posição de cauda, virar laço é tradução direta, não reescrita. Cada peça tem um destino fixo:

def soma(nums, acc=0):            # de cauda
    if not nums:
        return acc
    return soma(nums[1:], acc + nums[0])

def soma_laco(nums):              # a mesma função, desenrolada
    acc = 0                       # o valor inicial do parâmetro
    i = 0
    while i < len(nums):          # o caso base virou a condição de parada
        acc = acc + nums[i]       # o argumento da chamada virou atribuição
        i += 1
    return acc                    # o caso base virou o return do fim

Os parâmetros viram variáveis locais, o caso base vira a condição de parada, e a chamada recursiva vira a atualização dessas variáveis no fim da volta. É exatamente isso que a TCO faz por você em Elixir ou Kotlin: escrever de cauda é escrever um laço com sintaxe de recursão. Onde a linguagem não ajuda, o valor de saber a forma continua inteiro, porque é ela que torna a conversão trivial. E, de brinde, a versão em laço sai sem o nums[1:], ou seja, sem as cópias que faziam a recursiva custar O(n²).

Trampolim: quando a linguagem não ajuda

Se a linguagem não reaproveita o frame por você, dá para fazer isso na mão. A técnica se chama trampolim e o truque é simples: a função para de se chamar e passa a devolver a próxima chamada embrulhada, sem executá-la. Quem executa é um laço, que fica batendo nessa função como quem quica numa cama elástica.

def soma_passo(nums, acc=0):
    if not nums:
        return acc
    return lambda: soma_passo(nums[1:], acc + nums[0])   # devolve, não chama

def trampolim(f, *args):
    r = f(*args)
    while callable(r):     # enquanto vier função, salta de novo
        r = r()
    return r

Cada lambda desses é um thunk: um pedaço de trabalho adiado, guardado como valor. A função que devolve o thunk retorna de verdade, então o frame dela sai da pilha antes do próximo salto acontecer.

Rode com [1, 2, 3, 4] e siga a coluna da esquerda: a pilha sobe para 2 frames, volta para 1, sobe para 2, volta para 1, salto após salto. Nunca passa disso. À direita, o thunk aparece e some, que é o trabalho mudando de lugar: ele deixa de morar na pilha e passa a morar numa variável.

Depois arraste a régua "E se a lista tivesse n = ...". Em 999 a recursão direta ainda cabe, com 1.000 frames encostados no teto. Em 5.000 ela vira RecursionError, enquanto o trampolim faz 5.000 saltos com os mesmos 2 frames.

O trampolim brilha mesmo é onde reescrever como laço não é trivial, como na recursão mútua, duas funções que chamam uma à outra:

def par(n):
    if n == 0:
        return True
    return lambda: impar(n - 1)

def impar(n):
    if n == 0:
        return False
    return lambda: par(n - 1)

trampolim(par, 100000)   # True, com 2 frames o tempo todo

Não é de graça: cada salto aloca uma closure, o que deixa o trampolim mais lento que um while escrito à mão. Ele é a ferramenta certa quando a forma recursiva é a que expressa o problema (interpretadores, máquinas de estado, recursão mútua) e a linguagem não coopera.

De cauda nem sempre é mais rápido

A pergunta que fica em aberto no fim é a melhor parte do assunto: recursão de cauda é sempre mais rápida? Não.

Volte ao caso 7 do classificador, dobrar os valores de uma lista. A versão de cauda existe: o acumulador é a lista nova. Só que, ao ir consumindo head e colocando o resultado na frente do acumulador, ela monta a lista ao contrário: [1, 2, 3, 4] sai como [8, 6, 4, 2]. Para devolver na ordem certa, precisa de um reverse no fim, ou seja, uma passada extra sobre a lista inteira. Num benchmark simples, essa versão de cauda fica mais lenta que a recursão comum, que já constrói na ordem certa na volta.

E mesmo onde a de cauda ganha, o ganho pode ser modesto. Somando uma lista de 1.000 números, a versão comum fica só 1,14 vez mais lenta que a de cauda. Não é a diferença que o folclore promete.

A regra prática é boa o bastante para decidir no dia a dia:

Isso não é opinião solta: o guia de eficiência do Erlang lista "funções de cauda são muito mais rápidas que funções recursivas comuns" na seção Myths of Erlang Performance, ao lado de outros mitos clássicos como "list comprehension é lenta" e "string é lenta".

O que a recursão de cauda garante mesmo é memória: O(1) de pilha, sem teto de profundidade. Velocidade é outra conversa, e essa se mede.

Armadilhas e como praticar

"Escrevi de cauda em Python e ainda estourou." Vai estourar mesmo. A forma não otimiza nada sozinha; o botão sem TCO do primeiro visualizador existe para você ver isso acontecendo.

Mexer no sys.setrecursionlimit não resolve. Mudar o limite de 1.000 para 100.000 empurra a parede, mas a pilha real do interpretador continua finita, e o preço de bater nela é o processo morrer sem exceção.

Acumulador com valor inicial errado. É 0 para soma, 1 para produto, [] para lista. Para máximo, não use 0: com uma lista de negativos a resposta sai errada. Comece com o primeiro elemento (e trate a lista vazia como caso separado).

A ordem das cláusulas importa. Em Elixir, se a cláusula genérica vier antes da específica, ela engole tudo e as de baixo nunca rodam. Vá do mais específico para o mais genérico. E vale a pergunta que quase todo mundo faz na primeira vez: faltar uma cláusula não é erro de compilação, aparece só em produção, como FunctionClauseError, quando chega o valor que ninguém previu.

Confundir os dois nomes. Tail call é a última instrução ser uma chamada, qualquer chamada. Tail recursion é o caso particular em que essa chamada é para a própria função. TCO é o que a linguagem faz com qualquer um dos dois.

A lista sai ao contrário. Quando o acumulador é uma lista, ela sai invertida. Se a ordem não importa, não reverta e economize a passada.

Converter uma operação que não é associativa. Subtração, divisão e concatenação mudam de resultado quando a conta troca de lado, como o 9 contra o -15 que você viu ali em cima. Se precisar mesmo, inverta a lista antes ou ajuste o neutro, mas confira em papel primeiro.

Achar que TCO conserta complexidade. Ela conserta espaço, não tempo. O fibonacci ingênuo continua O(2ⁿ) em Elixir, com BEAM e tudo, porque a forma dele nem é de cauda (é o caso 5 do classificador). O que derrubou 2.692.537 chamadas para 31 foi o acumulador carregar os dois últimos valores, não a otimização da linguagem.

Os casos de borda que derrubam a submissão

Rode estes quatro na cabeça antes de submeter qualquer recursão de cauda:

• Lista vazia. O caso base tem que devolver o acumulador inicial, e ele precisa fazer sentido sozinho: soma([]) == 0 é razoável, maximo([]) não existe. Ou você devolve None de propósito, ou exige lista não vazia. No comparador, o preset "Lista vazia" mostra o pico de 1 frame dos dois lados.
• Um elemento só. É onde o acumulador inicial aparece na resposta sem disfarce. Com [7] e acc=0, a soma dá 7; com o produto e acc=0, dá zero, e o bug passa despercebido em listas maiores porque zera tudo do mesmo jeito.
• Todos os elementos iguais. Pega comparação trocada. Num acumulador de máximo tanto faz usar > ou >=, mas se o acumulador guarda o índice do máximo, > devolve o primeiro empate e >= devolve o último. Decida qual você quer antes de escrever.
• Profundidade maior que o teto. Em Python, qualquer entrada acima de ~1.000 níveis derruba a solução recursiva mesmo escrita perfeitamente de cauda. Em prova de LeetCode isso aparece como um caso de teste com 10⁴ ou 10⁵ elementos: ali a resposta é o while, ou o trampolim.

Cenários para testar nos visualizadores

• No classificador, ligue o Modo treino: o selo some, você decide sozinho olhando só o código e depois clica em "Revelar veredito". É esse reflexo que você quer treinar, e ele é a única coisa que você precisa saber fazer no código dos outros.
• No comparador, preveja o pico de frames antes de rodar: lista vazia, um elemento, sete elementos, com e sem TCO.
• No trampolim, ponha a régua em 999 e depois em 5.000. O primeiro passa, o segundo não. Repare que a coluna do trampolim não se move. Depois clique em Sortear algumas vezes: os saltos mudam de número, os 2 frames nunca mudam.

A ponte para os problemas

Os problemas no fim da página estão na ordem de resolver, e cada um treina um pedaço. A receita das quatro etapas resolve os cinco, e vale conferir se você chega nestes esqueletos sozinho antes de olhar.

1. Search in a BST já nasce de cauda, é o caso 6 do classificador. Escreva recursivo, veja que os dois return são só a chamada, e converta para while sem mudar uma vírgula da lógica: no = no.esq if alvo < no.val else no.dir.

2. Reverse Linked List é o acumulador em estado puro. O acumulador é a lista invertida, e ele cresce pela frente, que é justamente a operação O(1) da lista ligada:

def reverter(no, acc=None):
    if no is None:
        return acc               # acc já é a lista invertida
    prox = no.next
    no.next = acc                # o nó atual passa a apontar para o que já foi virado
    return reverter(prox, no)    # em posição de cauda

Escreva a versão iterativa depois e compare: acc virou prev, no virou curr, e o return recursivo virou o fim do while. É a mesma função duas vezes.

3. Fibonacci Number é a transformação top-down para bottom-up desta página, com a conta de chamadas que você já viu (2.692.537 contra 31 para n = 30). Aqui o acumulador é duplo: a e b carregam os dois últimos valores.

4. Pow(x, n) junta acumulador com divisão pela metade. O truque é que só o passo ímpar toca o acumulador:

def potencia(x, n, acc=1.0):
    if n < 0:
        return potencia(1 / x, -n, acc)    # expoente negativo: inverte a base
    if n == 0:
        return acc
    if n % 2 == 1:
        return potencia(x, n - 1, acc * x)  # tira o ímpar, guarda no acumulador
    return potencia(x * x, n // 2, acc)     # par: eleva a base ao quadrado

Com n = 1000 são 16 chamadas, todas em posição de cauda. Confira os dois casos de borda: n = 0 devolve o próprio neutro 1.0, e n negativo faz uma chamada a mais só para virar a base.

5. K-th Symbol in Grammar obriga a subir a árvore em vez de descer, que é a virada mental do bottom-up. O acumulador aqui é um booleano, "eu já inverti um número ímpar de vezes?":

def kth(n, k, inverteu=False):     # k é 1-indexado
    if n == 1:
        return 1 if inverteu else 0
    metade = 2 ** (n - 2)          # a linha n tem 2^(n-1) símbolos
    if k <= metade:
        return kth(n - 1, k, inverteu)
    return kth(n - 1, k - metade, not inverteu)

A segunda metade de cada linha é a primeira invertida, então cair nela troca o inverteu e o resto do caminho continua igual. São n chamadas, e nenhuma soma pendurada.

Depois disso, o caminho natural passa por Listas Ligadas, que é a estrutura em que tudo isto foi construído, por Pilhas, que é a estrutura que a recursão usa sem você ver, e por Programação Dinâmica, onde o acumulador vira tabela.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 2:21:37.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.

Este tópico também tem página própria, fora deste roadmap: Recursão: Programação Funcional.