Entendendo fundamentos de recursão

Se pra você:

Recursão é um tema obscuro ou quer entender mais um pouco sobre;
Tail call e TCO são meios de comunicação alienígena e;
Trampoline é nome de remédio

Então este artigo é pra você.

Aqui, vou explicar o que são estes termos de forma didática e os problemas que resolvem, com exemplos em Ruby. Mas não se preocupe pois os exemplos são bem simples de entender, mesmo porque os conceitos aqui mostrados são agnósticos a linguagem.

Portanto, venha comigo nesta viagem interminável.

✋
Para continuar, volte ao topo do post

O que é recursão

Em programas de computador, somos habituados a quebrar problemas grandes em problemas menores por meio do uso de funções ou métodos.

Recursão é, de forma extremamente simplificada, uma técnica na computação onde estes problemas são quebrados de forma que uma determinada função é executada recursivamente.

Com isto, a função "chama a si mesma" para resolver alguma computação e continuar sua execução.

Fibo para os íntimos

Um exemplo bastante clássico de recursão é descobrir, dada a sequência de Fibonacci, ou Fibo, qual número se encontra em determinada posição.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.........

Com isto, a função fib traria resultados como:

fib(0) = 0
fib(1) = 1
fib(2) = 1
...
fib(7) = 13
fib(10) = 55

Temos então uma possível implementação recursiva em Ruby:

def fib(position)
  return position if position < 2

  fib(position - 1) + fib(position - 2)
end

Este código, entretanto, não é performático. Ao tentar buscar o número da posição 10000 (dez mil) na sequência, o programa fica muito lento pois faz inúmeras chamadas recursivas redundantes.

                 fib(10)
             /                \
     fib(9)                 fib(8)
        /          \          /   \
fib(8)     fib(7)     fib(7)    fib(6)
  /      \       /       \       /   \
fib(7) fib(6) fib(6) fib(5) fib(6) fib(5)
   /    \     /     \     /     \     /    \
fib(6) fib(5) fib(5) fib(4) fib(5) fib(4) fib(5) fib(4)
  /   \   /   \   /   \   /   \   /   \   /   \   /   \
...

Consequentemente, quanto maior o input da função, o tempo de execução deste código tende a crescer de forma exponencial, que em notação Big-O seria O(2^n).

É possível reduzir esta complexidade?

E se tentarmos aplicar uma técnica onde a última chamada da função, ao invés de ser a soma de duas chamadas recursivas, passa a ser apenas uma chamada recursiva, sem realizar computações adicionais?

Esta técnica existe e é chamada de tail call, ou tail recursion.

Tail call

Tail call, ou TC, consiste em uma função recursiva onde a última chamada recursiva é a própria função sem computação adicional.

Com isto, reduzimos a complexidade de exponencial para linear, como se fosse um simples loop iterando em uma lista de inputs.

Em notação Big-O isto fica O(n), ou seja, a complexidade cresce de forma linear acompanhando o crescimento do input.

Exemplo em Ruby:

def fib(position, _current = 0, _next = 1)
  return _current if position < 1

  fib(position - 1, _next, _current + _next)
end

Portanto, o número de chamadas recursivas é reduzido drasticamente para algo do tipo:

fib(10, 0, 1)
fib(9, 1, 1)
fib(8, 1, 2)
fib(7, 2, 3)
fib(6, 3, 5)
fib(5, 5, 8)
fib(4, 8, 13)
fib(3, 13, 21)
fib(2, 21, 34)
fib(1, 34, 55)
fib(0, 55, 89)

Repara como que o número de chamadas recursivas diminuiu, ou seja, o código está seguindo um caminho mais linear com esta abordagem.

Assim, ao rodar o programa fib com TC, o tempo de execução é exponencialmente menor do que rodar sem TC, ficando dezenas de milhares de vezes mais rápido.

✋
Claramente um programa que leva tempo exponencial é péssimo em termos de performance, não?

# Sem TC
fib(30) # 0.75 segundos

# Com TC
fib(30) # 0.000075 segundos

Voltando ao exemplo de fib(10000), ao rodar com TC, vemos que a execução é muito mais rápida, porém:

recursion/fib.rb:10:in `fib_tc': stack level too deep (SystemStackError)
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'
        from recursion/fib.rb:10:in `fib_tc'

Uh oh, um stack overflow!

Para entender o que está acontecendo, vamos primeiro entender o que raios é uma stack e stack overflow.

Stack e stack overflow

Quando um programa é executado, é alocada na memória uma estrutura de dados em formato de pilha, chamada Stack, que é utilizada para guardar os dados que estão sendo utilizados em uma função em execução.

✋
Há também outra estrutura na memória do programa chamada Heap, que não é uma pilha e tem outras características que vão além do escopo deste artigo. Para entender recursão, focamos apenas na stack

Quando o programa entra em uma função ou método, cada dado é inserido (push) na stack. Ao terminar a função, é feita a remoção (pop) de cada dado.

A cada chamada de função, é atribuído um novo stack frame. Como uma chamada recursiva nunca termina, o runtime não sabe que é preciso fazer "pop" dos dados e finalizar o frame, então a cada chamada, uma nova stack frame é criada e mais elementos são adicionados à stack.

Adivinha o que acontece quando adicionamos muitos dados na stack a ponto de ultrapassar seu limite na memória do computador?

Sim, acontece o famigerado Stack overflow 💥🪲, e isto explica aquele erro no Ruby ao rodar fib de 10000 com tail call.

✋
Então quer dizer que calcular o fib de 10000 é um problema impossível de resolver com recursividade?

Calma, algumas linguagens empregam uma técnica de otimização que consiste em utilizar a chamada TC com apenas um stack frame, garantindo assim que cada chamada recursiva seja tratada como se fosse uma iteração num loop primitivo.

Com isto, é feita a manipulação dos argumentos e dados da função em uma única stack frame, exatamente como se tivéssemos escrito um loop primitivo. E consequentemente, novas chamadas recursivas de cauda não vão provocar estouro na pilha.

A esta técnica chamamos de Tail call optimization, ou TCO.

Tail call optimization

Devido a sua natureza imperativa, e assim como diversas outras linguagens de propósito geral, Ruby não traz suporte nativo a TCO.

Geralmente esta funcionalidade é mais encontrada em linguagens com forte inclinação ao paradigma funcional, e não ao imperativo.

Mas em Ruby é possível habilitar o modo TCO com uma simples configuração na instrução do runtime do Ruby (YARV), e assim conseguimos executar fib de 10000 sem dor.

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

def fib(position, _current = 0, _next = 1)
  return _current if position < 1

  fib(position - 1, _next, _current + _next)
end

# TC com TCO
fib(10000) # 0.02 segundos

Superb! Com TCO habilitado, uma fib 10000 com tail call é executada em 0.02 segundos!

Vale lembrar que TCO é uma técnica utilizada não apenas em recursão mas também em otimização de geração de instruções em compiladores,
mas isto foge ao escopo deste artigo.

✋
Okay, mas e quando não for possível habilitar TCO para recursão de cauda ou eu estiver programando em uma linguagem que não tenha suporte a TCO?

Trampoline para o resgate.

Trampoline

Para entendermos trampoline, vamos pensar no problema e em uma possível solução.

Se pensarmos com inteligência, podemos inicialmente concluir que a recursão deve ser evitada, e esta é a premissa número um.

def fib(position, _current = 0, _next = 1)
  return _current if position < 1

  ###################################
  #### Devemos evitar isso!!!!!! ####
  ###################################
  fib(position - 1, _next, _current + _next)
end

Premissa dois, ao invés de retornar uma chamada recursiva diretamente, e se a retornarmos encapsulada em uma estrutura de função anônima que guarda contexto para ser executada em outro contexto?

Sim, tipo uma closure ou lambda para os mais atentos

Em Ruby, podemos utilizar o conceito de lambdas.

def fib(position, _current = 0, _next = 1)
  return _current if position < 1

  lambda do
    fib(position - 1, _next, _current + _next)
  end
end

Se chamarmos result = fib(0), por causa da primeira linha de short-circuit (position < 1), o retorno do método é 0.

Mas se chamarmos result = fib(10), o retorno não será uma chamada recursiva, mas sim o retorno será uma função anônima (lambda).

Com isto, o método é então finalizado e a stack é limpa, ou seja, é feito o pop dos dados de dentro do método.

Como lambdas guardam contexto, se chamarmos result.call, a lambda é executada com o contexto anterior, que pode retornar o número final (caso entre no short-circuit) ou outra lambda com o novo contexto.

E assim, ficamos em loop até termos o valor final, enquanto o retorno atual continuar sendo uma lambda. Conseguiu entender o que podemos fazer?

Sim, um loop!

result = fib(10000)

while result.is_a?(Proc)
  result = result.call
end

puts result

Output (um número mesmo muito grande):

33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

🔑 Ponto-chave
E com isto, amigues, temos a técnica trampoline: um loop primitivo não-recursivo que fica chamando outra função escrita de forma recursiva mas que retorna uma lambda com contexto, até chegar ao valor final.

Este código, sem TCO, para o fib de 10000, leva 0.04 segundos, um resultado muito próximo a TCO e sem causar stack overflow.

Incrível, não? Agora não há desculpas para não escrever uma função de modo recursivo em linguagens que não trazem suporte a TCO 😛

Conclusão

Neste artigo, o intuito foi trazer alguns conceitos que tocam no tema recursão. Estes conceitos fazem overlap com temas muito acadêmicos que, por vezes, dificultam o entendimento de pessoas que estão iniciando na área ou que não têm um background muito acadêmico.

Espero ter esclarecido de forma didática o assunto recursão, se puder deixe nos comentários qualquer correção ou informação relevante.

Referências

https://twitter.com/leandronsp/status/1672043065001869312
https://twitter.com/JeffQuesado/status/1671954585987022882
https://en.wikipedia.org/wiki/Fibonacci_sequence
https://en.wikipedia.org/wiki/Recursion
https://www.geeksforgeeks.org/stack-data-structure/
https://en.wikipedia.org/wiki/Tail_call
https://en.wikipedia.org/wiki/Trampoline_(computing)
https://nithinbekal.com/posts/ruby-tco/
https://www.bigocheatsheet.com/
https://ruby-doc.org/core-3.1.0/RubyVM/InstructionSequence.html#method-c-compile_option

Blog