Imagine que você tem um quebra-cabeça enorme na sua frente, e cada encaixe entre duas peças desse quebra-cabeça é um problema. Às vezes, resolver um problema grande significa que você precisa resolver outros problemas menores primeiro. A recursividade em Python é como pedir ajuda para resolver esses problemas menores até que você resolva o problema grande.

Falando de outra forma, recursividade é você a função dentro dela mesma, para atender determinada demanda, observando três princípios:

• Um algoritmo recursivo deve ter um caso básico, ou condição de término;
• Um algoritmo recursivo deve mudar o seu estado e se aproximar do caso básico;
• Um algoritmo recursivo deve chamar a si mesmo, recursivamente;

O que é recursividade?

Recursividade é o mecanismo de programação no qual uma definição de função ou de outro objeto refere-se ao próprio objeto sendo definido. Assim função recursiva é uma função que é definida em termos de si mesma.

Como funciona na prática?

Agora vou lhe apresentar dois códigos: O primeiro deles é de modo iterativo, utilizando um for para percorrer toda uma lista. E no segundo é um código recursivo que faz a mesma função do for, porém chamando a mesma função imprimi_recursiva dentro dela mesma.

• Abaixo, Código Iterativo:

def imprime(l):
for i in range(len(l)):
  print(l[i])

• Abaixo Código Recursivo:

def imprime_recursivo(l, i=0):
if i < len(l):
  print(l[i])
  imprime_recursivo(l, i+1)

Agora que você entende melhor como a recursividade funciona em Python, podemos explorar essa técnica poderosa para resolver uma variedade de problemas de forma elegante e eficiente.

Vamos verificar como calcular o n-ésimo termo de Fibonacci. Sabendo que Fibonnati é uma sequência infinita de números que começa com 0 e 1, onde os números seguintes são sempre a soma dos números anteriores, portanto: 0, 1, 1, 2, 3, 5, 8, 13, 21,34...

• Abaixo Código Iterativo:

def fib_it(n):
res = n
a, b = 0, 1
for k in range(2, n+1):
  res = a + b
  a, b = b, res
return res

• Abaixo Código Recursivo:

def fib_rec(n):
if n < 2:
  return n
else:
  return fib_rec(n-1) + fib_rec(n-2)

Estimativa de tempo para Fibonacci

Ao utilizar a função recursiva, ela executa diversas vezes todo o código, utilizando assim mais recursos computacionais e consecutivamente demorando mais para obter o mesmo resultado utilizando uma função iterativa. Porém às vezes é necessário utilizar a função recursiva para resolver determinando problema ou questão, e há uma forma de resolver a questão do uso excessivo destes recursos fazendo a alocação de certos resultados em listas dentro das funções recursivas.

Este recurso é chamado Memoização que em termos técnicos é definido como: Técnica de otimização que armazena os resultados de chamadas de funções custosas, e que retorna o valor armazenado quando a função é chamada novamente.

• Segue exemplo abaixo do n-ésimo termo do Fibonacci utilizando a memoização:

m = dict()
def fat(n):
if n == 0:
  return 1
elif m.get(n) != None:
  return m[n]
else:
  m[n] = n * fat(n-1)
  return m[n]

Para finalizar, observo que como programadores devemos sempre buscar as melhores formas de performar nossos códigos, sempre primeiramente fazendo o código funcionar de forma prática, e ir aprimorando-o para torna-los mais eficientes, consumindo menos recursos. Porém para certos problemas não há soluções já prontas, então devemos conhecer todos os artifícios que podemos utilizar para resolver nossas demandas.

Vamos Disseminar os Conhecimentos e Transbordar Tudo o que Aprendemos!

Segue o Link do meu GitHub: https://github.com/Carlos-CGS

Segue o Link do meu LinkedIn: https://www.linkedin.com/in/carlos-cgs/