Explique o conceito de funções recursivas e como elas funcionam

Uma função recursiva é uma função que chama a si mesma para resolver um problema. Ela divide o problema em subproblemas mais simples do mesmo tipo, até atingir um caso base em que não são necessárias mais chamadas.

Princípio de funcionamento:

• A função chama a si mesma com parâmetros modificados, aproximando a solução do caso base.
• Quando o caso base é atingido, a função começa a retornar resultados ao longo da cadeia de chamadas.

Exemplo: cálculo do fatorial de um número n (n!)

def factorial(n):
    if n == 0:
        return 1  # caso base
    else:
        return n * factorial(n - 1)  # chamada recursiva

Aqui, factorial chama a si mesma com n-1, até chegar a 0, momento em que começa a retornar valores para cima na cadeia.

Recursão é útil para tarefas que se dividem naturalmente em sub-tarefas semelhantes, como percorrer árvores, calcular números de Fibonacci, ordenar, etc.