Recursão

Recursão é quando uma função chama a si mesma durante sua execução. Isso pode ser útil para resolver problemas que podem ser divididos em subproblemas menores, como percorrer estruturas aninhadas ou calcular sequências matemáticas.

Vamos imaginar que você tem uma pilha de caixas, e está procurando uma chave. Dentro de cada caixa pode haver outra caixa, e assim por diante. Um algoritmo recursivo para esse problema poderia ser assim:

1def busca_caixa(item):
2    if item.eh_caixa():
3        busca_caixa(item)
4    elif item.eh_chave():
5        return item
6    else:
7      return None

Numa função recursiva é muito fácil acabar criando um loop infinito. Com base nisso podemos separar ela em duas partes:

• Caso recursivo: Quando a função chama a si mesma
• Caso base: Quando a função não chama a si mesma.

1def regressiva(i: int)
2    print(i)
3    if i <= 1: # Caso base
4        return
5    else: # Caso recursivo
6        regressiva(i - 1)

A recursão é muito utilizada em algoritmos como cálculo de fatorial, Fibonacci, busca em árvores, entre outros.