Qual é o limite da recursão?

O que é recursão?

Em resumo, recursão é o processo de se autorreferenciar. Um exemplo disso seria um espelho apontado para outro.

A recursão é utilizada em vários meios, desde o design até na linguística

Na programação a recursividade é utilizada para otimizar algumas soluções de problemas.

Como esse não é o intuito do post, não vou me aprofundar na definição de recursão.

Causos da minha vida

Recentemente eu participei da XXIV Maratona de programação e lá me deparei com alguns problemas cujo o tamanho da entrada a se calcular poderia ser até 1 000 000 000 (1 Bilhão)

Logo me lembrei das aulas de programação e das maravilhas da recursividade, mas… Sera que meu humilde Python da conta?

Spoiler: Não

Mas… POR QUE???

Na programação um código recursivo chama ele mesmo até que atinja uma condição de parada.

Exemplo:

def fibonacci(n):
  if n < 2: 
    return 1

  return self.calc(n-1) + self.calc(n-2)

Nesse caso a condição de parada é “if n < 2”

Então o quanto maior for o n mais vezes a recursão vai ser aberta e vale lembrar que isso gera um apontamento na memoria do computador

Então mesmo sendo rápido, a recursividade começa a se tornar custosa para o computador

E é claro que eu não ia perder a oportunidade de destrinchar ao máximo os limites disso :v

Demonstração

Todos os códigos estão no meu repositório no GitHub https://github.com/MatheusMuriel/ProgramacaoDinamica (Alias segue eu la <3)

Existe a sequencia de Fibonacci, um numero de fibonacci é igual a soma dos dois números anteriores.

Um caso perfeito para recursão.

Então eu criei um algorítimo puramente recursivo e fiz um benchmark de seus tempos.

Ok, está rápido, mas quando vc chega perto do 50, esse algoritmo já não funciona mais.

Uma forcinha pra recursão

Quando olhei isso eu lembrei das aulas de Inteligencia Artificial em que o professor mostrou uma técnica de programação dinâmica que evitava recalculo. Essa técnica se chamava Memoization

O memoization consiste em guardar os resultados de cada operação em uma tabela de memoria, assim quando vc precisar saber o resultado de fib(50) primeiro vc verifica na tabela se isso já foi calculado, se sim vc só consulta o valor na tabela, se não vc calcula e salva na tabela.

Combinado eu tbm aumentei o limite de recursão do python adicionando sys.setrecursionlimit(1000000000) no meu código

Assim a recursão acaba ficando mais rápida. Muito mais rápida. MUITO MAIS RÁPIDA.

Tão rápida que foi capaz de calcular o numero 16869 da sequencia de fibonacci em menos de 1 segundo

– E como vc sabe que isso ta certo em???

Boa pergunta! Eu validei pelo WolframAlpha

Mas nessa vida nem tudo são flores.

A partir de um valor muito grande a recursão é aberta tanto que esgota os endereços de memoria no computador e o computador mata o processo

Grrrr

E agora Muriel???

Calma lá, ainda tem mais.

(como se 16869 não fosse um numero estupidamente grande )

As vezes é preciso abrir mão

Sim sim, a recursão é muito legal, maravilhosa, fácil de entender e programar… Mas chega uma hora que é preciso esquecer os velhos conhecimentos, aqui estamos entrando no submundo da programação extrema.

Ok, memoria é um problema.

E se ao invés de guardar todos os resultados na tabela de memoria a gente limpar os resultados que não são muito usados?

Mas mesmo assim a recursão vai abrir muito e esgotar a memoria

Assim, podemos fazer um forzão raiz e partir pro abraço

Assim eu fiz, eu mantive a estrutura principal do calculo em um for e os cálculos de valores específicos dentro de um algorítimo recursivo

E até onde ele chegou?

Ate o 400000º (400 Mil) numero de Fibonacci

(Pensa em um cara que ficou feliz quando viu esse resultado)

Pra calcular isso o código demorou aproximadamente 3,26 Minutos

E é isso… Agora estou pensando em uma nova abordagem para calcular um numero ainda maior

FOCO NO 1 MILHÃO

Assim que eu tiver mais resultados eu posto aqui.

Se quiser testar em seu próprio computador basta clonar meu repositório no GitHub instalar as bibliotecas do requirements.txt e ser feliz.

Se eu tiver falado algo errado e vc tiver alguma correção sintase a vontade para comentar ou entrar em contato comigo.