A recursão em programação é um conceito onde uma função chama a si mesma para resolver um problema. É uma forma de "dividir para conquistar", onde um problema maior é decomposto em subproblemas menores da mesma natureza.

O que é Recursão de Função

Uma chamada de função aninhada ocorre quando uma função é definida dentro de outra. A chamada recursiva de função é um caso especial de aninhamento, onde a função chama a si mesma dentro de seu próprio corpo. Sem uma condição de parada deifnida, uma função recursiva pode entrar em um loop infinito, levando a um erro de estouro de pilha (stack overflow).

Exemplo de chamada recursiva sem condição de parada:

def funcao_infinita():
   print('Chamando a mim mesma...')
   funcao_infinita()

# funcao_infinita() # Isso causaria um loop infinito e um erro
   

Recursão Direta

A recursão direta ocorre quando uma função chama explicitamente a si mesma em seu corpo.

Um exemplo prático é calcular a idade de uma pessoa após 'n' anos, onde cada ano a idade aumenta em 2. Para isso, utilizamos a pasagem de parâmetros e o escopo de variáveis.

lista_idades = [16] # Idade inicial

def calcular_idade_futura(anos):
   if anos == 0:
       return lista_idades[0]
   
   idade_anterior = calcular_idade_futura(anos - 1)
   idade_atual = idade_anterior + 2
   return idade_atual

print(f"Idade após 5 anos: {calcular_idade_futura(5)}")
   

Recursão Indireta

A recursão indireta acontece quando uma função chama outra função, que por sua vez chama a função original, criando um ciclo de chamadas.

def funcao_a():
   print('Executando funcao_a')
   funcao_b(20)

def funcao_b(valor):
   print(f'Executando funcao_b com valor: {valor}')
   funcao_a()
   
# Para iniciar o ciclo, chame uma das funções:
# funcao_a() 
# funcao_b(20) 
   

Considerações sobre Recursão

• Decomposição: Em cada etapa recursiva, o problema deve ser reduzido em tamanho, aproximando-se da condição de parada.
• Condição de Parada (Base Case): É fundamental definir uma condição clara que encerrre a recursão. Quando essa condição é atingida, a função para de se chamar e começa a retornar os resultados das chamadas anteriores (backtracking).

Através desse processo repetitivo e do retorno de valores, um resultado final é obtido.

Exemplo: Validação de Parênteses

Dado uma string contendo apenas '(', ')', '{', '}', '[' e ']', determinar se a string é válida. Uma string é válida se:

• Os colchetes abertos são fechados pelos mesmos tipos de colchetes.
• Os colchetes abertos são fechados na ordem correta.
• Uma string vazia também é considerada válida.

Exemplos:

• Entrada: "()" Saída: Verdadeiro
• Entrada: "()[]{}" Saída: Verdadeiro
• Entrada: "(]" Saída: Falso
• Entrada: "([)]" Saída: Falso
• Entrada: "{[]}" Saída: Verdadeiro

def eh_valido(s: str) -> bool:
   '''
   Verifica se uma string de parênteses é válida usando recursão.
   '''
   if not s:
       return True # String vazia é válida

   # Procura por pares válidos adjacentes e os remove recursivamente
   if '()' in s:
       return eh_valido(s.replace('()', '', 1))
   elif '[]' in s:
       return eh_valido(s.replace('[]', '', 1))
   elif '{}' in s:
       return eh_valido(s.replace('{}', '', 1))
   else:
       # Se não houver pares para remover e a string não estiver vazia, é inválida
       return False

# Testando a função
teste1 = "()"
teste2 = "()[]{}"
teste3 = "(]"
teste4 = "([)]"
teste5 = "{[]}"
teste6 = ""

print(f'"{teste1}" é válido? {eh_valido(teste1)}')
print(f'"{teste2}" é válido? {eh_valido(teste2)}')
print(f'"{teste3}" é válido? {eh_valido(teste3)}')
print(f'"{teste4}" é válido? {eh_valido(teste4)}')
print(f'"{teste5}" é válido? {eh_valido(teste5)}')
print(f'"{teste6}" é válido? {eh_valido(teste6)}')