Funções Recursivas em Python

Introdução

Bem-vindo ao reino mítico da Pitonesia, um grande império renomado pelo seu uso avançado de construtos mágicos e matemáticos. Como chefe da guarda real do reino, você é encarregado da defesa do artefato mais precioso do império: o Cristal Recursivo. As lendas afirmam que ele foi criado usando um código antigo que se repete dentro de si mesmo para criar uma fonte infinita de energia. Para entender e proteger melhor este artefato, você deve dominar a arte da recursão em Python - a mesma habilidade que foi usada para criá-lo.

Seu objetivo será empunhar o poder da recursão para resolver problemas complexos que não podem ser facilmente resolvidos por meios convencionais. Ao fazer isso, você garantirá a segurança da riqueza e do conhecimento do império contra aqueles que buscam usá-los indevidamente. Prepare-se para embarcar em uma jornada através do tempo e do código, desvendando os mistérios das funções recursivas.

Entendendo a Recursão

Nesta etapa, você aprenderá o conceito básico de recursão e como implementá-lo em Python. Uma função recursiva é aquela que chama a si mesma para resolver um problema. A chave para projetar uma função recursiva é garantir que ela tenha um caso base (base case), que é uma condição que interrompe a recursão, e um caso recursivo (recursive case), que é onde a função chama a si mesma.

Vamos começar criando uma função recursiva simples que calcula o fatorial de um número. O fatorial de um número n é o produto de todos os inteiros positivos menores ou iguais a n.

Abra ~/project/factorial.py no seu editor de texto preferido e adicione o seguinte código:

def factorial(n):
    if n == 0:  ## Base case
        return 1
    else:        ## Recursive case
        return n * factorial(n - 1)

## Example usage
print(factorial(5))

Para executar o código, use o seguinte comando:

python3 factorial.py

O resultado esperado deve ser 120, pois 5! = 5 * 4 * 3 * 2 * 1 = 120.

Recursão com Múltiplos Casos Base

Em seguida, você aprenderá como construir uma função recursiva com múltiplos casos base. Vamos criar uma função fibonacci em um arquivo chamado fibonacci.py, que calculará a sequência de Fibonacci até o n-ésimo número. A sequência de Fibonacci é uma série de números onde cada número é a soma dos dois anteriores, começando de 0 e 1.

Insira o seguinte código em ~/project/fibonacci.py:

def fibonacci(n):
    if n == 0:  ## First base case
        return 0
    elif n == 1:  ## Second base case
        return 1
    else:         ## Recursive case
        return fibonacci(n - 1) + fibonacci(n - 2)

## Example usage
print(fibonacci(10))

Execute o código com o comando:

python3 fibonacci.py

A saída esperada deve ser 55, pois é o 10º número na sequência de Fibonacci.

Resumo

Neste laboratório, aprofundamos o conceito de recursão em Python, aplicando-o a duas sequências matemáticas diferentes. O processo de pensamento do design girou em torno da criação de uma história intrigante que torna o aprendizado da recursão divertido e relevante. As tarefas foram estruturadas, partindo de um caso base único mais simples de fatoriais para um cenário ligeiramente complexo com múltiplos casos base em Fibonacci, para garantir uma compreensão abrangente.

Ao final do laboratório, você não apenas se tornou proficiente em escrever funções recursivas, mas também absorveu a importância dos casos base e a mecânica por trás das chamadas recursivas. Agora você possui a chave para utilizar algoritmos recursivos para resolver problemas do mundo real, uma habilidade tão valiosa quanto o mítico Cristal Recursivo da Pitonésia.