Algoritmos Recursivos

2.1 Percorrendo Árvore de Arquivos

Vamos dar uma olhada em um algoritmo recursivo para percorrer uma árvore de arquivos. O algoritmo irá percorrer um diretório e todos os seus subdiretórios, listando todos os arquivos e pastas.

import os

def list_files_recursive(directory, indent=0):
    # Obtém a lista de todos os arquivos e pastas no diretório atual
    items = os.listdir(directory)
                
    for item in items:
        # Cria um caminho completo para o arquivo ou pasta
        path = os.path.join(directory, item)
                    
        # Exibe com recuo para melhor percepção da estrutura
        print(' ' * indent + item)
                    
        # Se for uma pasta, percorre seu conteúdo recursivamente
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# Exemplo de uso
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

Como isso funciona?

1. Função list_files_recursive(directory, indent=0):
   • directory — o diretório atual cujo conteúdo queremos listar.
   • indent — o nível atual de recuo para mostrar a aninhamento de arquivos e pastas.
2. Obtém a lista de todos os arquivos e pastas no diretório atual usando os.listdir(directory).
3. Passa por cada item na lista items.
4. Cria o caminho completo para o item usando os.path.join(directory, item).
5. Exibe o nome do item com recuo, que aumenta em 4 espaços para cada nível de aninhamento.
6. Verifica se o item é uma pasta usando os.path.isdir(path). Se for, chama recursivamente list_files_recursive(path, indent + 4) para percorrer seu conteúdo.

Exemplo de saída:

Suponha que temos a seguinte estrutura de diretórios:

root_directory/
    file1.txt
    dir1/
        file2.txt
        file3.txt
        dir2/
            file4.txt
    file5.txt

Ao executar a função list_files_recursive(root_directory) teremos a seguinte saída:

file1.txt
dir1
    file2.txt
    file3.txt
    dir2
        file4.txt
file5.txt

Este algoritmo percorre recursivamente a árvore de diretórios, exibindo todos os arquivos e pastas considerando sua aninhamento.

2.2 Torres de Hanói

Problema das Torres de Hanói

Torres de Hanói é um problema recursivo clássico que envolve mover discos de uma haste para outra usando uma haste auxiliar.

Regras:

1. Você pode mover apenas um disco de cada vez.
2. Um disco só pode ser colocado em uma haste vazia ou sobre um disco maior.
3. Você deve mover todos os discos de uma haste para outra, usando a haste auxiliar.

Aqui está um algoritmo recursivo para resolver esse problema:

O algoritmo das Torres de Hanói resolve o problema da seguinte forma:

1. Mover n - 1 discos da haste inicial para a auxiliar, usando a haste alvo.
2. Mover o disco restante da haste inicial para a alvo.
3. Mover n - 1 discos da haste auxiliar para a alvo, usando a haste inicial.

Exemplo em Python

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Mover disco 1 de {source} para {target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Mover disco {n} de {source} para {target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# Exemplo de uso:
n = 3  # Número de discos
hanoi_tower(n, 'A', 'C', 'B')
        

Como funciona?

Base do caso:

Se houver apenas um disco (n == 1), ele pode ser movido diretamente da haste inicial para a alvo.

if n == 1:
    print(f"Mover disco 1 de {source} para {target}")
    return

Acaso Recursivo:

Passo 1. Mover discos n-1 da haste inicial para a auxiliar, usando a haste alvo.

hanoi_tower(n - 1, source, auxiliary, target)

Passo 2. Mover disco n da haste inicial para a alvo.

print(f"Mover disco {n} de {source} para {target}")

Passo 3. Mover discos n - 1 da haste auxiliar para a alvo, usando a haste inicial.

hanoi_tower(n - 1, auxiliary, target, source)

Exemplo de saída:

Para três discos (n = 3) nas hastes A, B e C, o programa irá exibir:

Mover disco 1 de A para C
Mover disco 2 de A para B
Mover disco 1 de C para B
Mover disco 3 de A para C
Mover disco 1 de B para A
Mover disco 2 de B para C
Mover disco 1 de A para C

2.3 Floco de Neve de Koch

Desenhar um floco de neve usando recursão é uma tarefa interessante, que é frequentemente usada para estudar fractais. Uma maneira simples de desenhar um floco de neve é usar a curva de Koch, que é uma curva fractal.

Algoritmo para desenhar o Floco de Neve de Koch

A curva de Koch é construída da seguinte forma:

• Comece com uma linha reta.
• Divida cada segmento em três partes e substitua a parte central por uma pequena curva, parecendo um "bico".
• Repita este processo recursivamente para cada segmento.

Passo a passo

• Início: Desenhe o segmento inicial.
• Divisão: Divida cada segmento em três partes.
• Substitua a parte central: No segmento central, desenhe um "bico", composto por duas linhas formando um ângulo de 60 graus.
• Repita o processo: Continue este processo para cada segmento.

Exemplo em Python usando a biblioteca Turtle

import turtle

def draw_koch_curve(t, length, depth):
    if depth == 0:
        t.forward(length)
    else:
        length /= 3.0
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
        t.right(120)
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
            
def draw_snowflake(t, length, depth):
    for _ in range(3):
        draw_koch_curve(t, length, depth)
        t.right(120)
            
# Configuração da tela
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Configuração da tartaruga
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Desenhar floco de neve
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Terminar desenho
turtle.done()
            

Como funciona?

1. Função draw_koch_curve(t, length, depth):

• t: a tartaruga que desenha.
• length: comprimento do segmento.
• depth: profundidade da recursão, determinando o nível de detalhe.

2. Caso base:

Se depth for igual a 0, a tartaruga desenha um segmento reto.

if depth == 0:
    t.forward(length)
        

3. Caso recursivo:

Divida o segmento em três partes e aplique draw_koch_curve recursivamente em cada parte, adicionando giros.

length /= 3.0
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)
t.right(120)
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)

4. Função draw_snowflake(t, length, depth):

Desenha três curvas de Koch, conectadas em um floco de neve.

for _ in range(3):
    draw_koch_curve(t, length, depth)
    t.right(120)

Como rodar o código?

• Certifique-se de que você tem a biblioteca Turtle instalada (pip install PythonTurtle).
• Copie e cole o código em um arquivo .py e execute-o. Você verá um floco de neve sendo desenhado na tela.

Este algoritmo permite visualizar a estrutura fractal do floco de neve com o uso de conceitos simples de recursão e construções geométricas.