Conceito de Recursão

1.1 Definição de recursão e seus conceitos básicos.

Recursão é quando algo faz a si mesmo repetidamente. Imagine que você tem uma instrução, e uma parte dessa instrução diz para seguir a própria instrução. É como se você desse um comando para repetir o próprio comando.

Exemplos da vida real:

Espelhos um de frente para o outro:

Imagine que você está entre dois espelhos. Você vê seu reflexo e no reflexo também vê seu reflexo, e isso continua repetidamente. Este é um exemplo de recursão, porque cada espelho mostra o reflexo do outro espelho.

Matrioshkas:

Matrioshka é uma boneca que contém outra boneca dentro, e dentro dessa, outra, e assim por diante. Quando você chega à menor boneca, não há mais nada para abrir. Isso é como um caso base na recursão — o momento em que você deve parar.

Dividindo a pizza:

Imagine que você está dividindo uma pizza ao meio. Então, você pega uma metade e divide novamente ao meio, e continua assim até que as fatias fiquem pequenas demais para dividir. Dividir em partes é um processo recursivo, e o momento em que você não pode mais dividir uma fatia é o caso base.

Importante! Recursão não é simplesmente repetir um comando infinitamente, é mais sobre dividir uma tarefa complexa em partes, sendo que o método para resolver cada parte é semelhante ao método para resolver a tarefa inteira.

Como isso funciona?

Para entender a recursão, você precisa conhecer dois conceitos principais:

• Caso base: esta é a condição em que a recursão para. Por exemplo, no exemplo das matrioshkas, o caso base é quando você abre a menor matrioshka e não há mais nada dentro.
• Caso recursivo: esta é a situação em que a tarefa se repete com partes menores. No exemplo da pizza, você divide uma fatia, depois divide a metade, e assim por diante.

Por que isso é útil?

Recursão ajuda a resolver problemas complexos, dividindo-os em partes mais simples. Em vez de resolver toda a tarefa de uma vez, você a resolve em pedaços.

Outros exemplos da vida:

História dentro de uma história:

Imagine que o herói de uma história conta outra história, e o herói dessa história começa a contar mais uma história. Quando uma das histórias termina, você volta para a história anterior. O caso base é quando a última história termina.

Desenho recursivo:

Você desenha um grande triângulo, e então em cada canto desse triângulo desenha um triângulo menor, e continua até que os triângulos fiquem pequenos demais para desenhar. O caso base é quando o triângulo fica tão pequeno que não pode ser desenhado.

1.2 Caso base: definição e exemplos.

Caso base é a condição que encerra as chamadas recursivas e permite que a função retorne um valor específico. Normalmente é a solução mais simples e óbvia para o problema, que não exige mais recursão.

Exemplos de caso base:

Fatorial de um número:

O fatorial de um número n é representado como F(n) == 1*2*3*…*n. Também é óbvio que F(n) == n* F(n-1).

Caso base: o fatorial de 0 ou 1 é igual a 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Caso base
    else:
        return n * factorial(n - 1)
        

Números de Fibonacci:

Números de Fibonacci são a sequência: 1, 1, 2, 3, 5, 8, 13, … Onde cada número seguinte é a soma dos dois anteriores. Para F(n) == F(n-1) + F(n-2)

Caso base: os dois primeiros números de Fibonacci são 1, portanto o "número zero" de Fibonacci é 0. Ou F(0) = 0 e F(1) = 1.

def fibonacci(n):
    if n == 0:
        return 0  # Caso base
    elif n == 1:
        return 1  # Caso base
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 Caso recursivo: definição e exemplos

Caso recursivo é a parte da função que resolve o problema chamando a si mesma com novos parâmetros, que aproximam a solução do caso base. Cada chamada recursiva diminui ou modifica o problema para que, eventualmente, se atinja o caso base.

Exemplos de caso recursivo:

Fatorial de um número:

Caso recursivo: o fatorial de um número n é n multiplicado pelo fatorial de n-1.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Caso base
    else:
        return n * factorial(n - 1)  # Caso recursivo
        

Números de Fibonacci:

Caso recursivo: F(n) é igual à soma de F(n-1) e F(n-2).

def fibonacci(n):
    if n == 0:
        return 0  # Caso base
    elif n == 1:
        return 1  # Caso base
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Caso recursivo
        

1.4 Exemplos de algoritmos recursivos

1. Percurso em uma árvore binária:

Exemplo de percurso em ordem "in-order".

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# Exemplo de uso:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. Busca do elemento máximo em uma lista:

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # Caso base
    else:
        max_of_rest = find_max(lst[1:])  # Caso recursivo
        return max(lst[0], max_of_rest)
        
# Exemplo de uso:
print(find_max([1, 5, 3, 9, 2]))  # Saída: 9
        
        

3. Busca binária recursiva:

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Caso base: elemento não encontrado
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Caso base: elemento encontrado
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Caso recursivo
    else:
        return binary_search(arr, target, left, mid - 1)  # Caso recursivo 
# Exemplo de uso:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Saída: 4