Aprenda a utilizar recursão em Python com um exemplo prático de navegação em sistemas de arquivos. Para isto será preciso entender a pilha de execução de um software.
O que é recursão?
A primeira vez que vi recursão eu fiquei com um grande ponto de interrogação na cabeça. Parecia que eu não ia entender nunca. Mas não é tão difícil quanto parece à primeira vista, a recursão te permite repetir passos assim como um laço for ou while mas faz isso de uma forma diferente.
A recursão nada mais é do que uma função que cham a si mesma. E a parte mais importante dela é saber identificar o caso base, pois ele é o ponto de parada, que garante que a função não execute infinitamente. Ficou confuso? Vamos ver com um exemplo que fica mais fácil de entender.
Entendendo a pilha de execução
Antes de nos aprofundarmos mais, vamos entender como funciona a pilha de execução de um programa. Primeiro precisamos entender que existe uma função especial em python chamada __main__ que é o ponto inicial de todos os programas em pyhon.
O código é executado linha a linha, então o python busca a primeira instrução do arquivo e começa a executar. Veja o gráfico abaixo:
O Python (e outras linguagens de programação também) mantém uma pilha que indica ao programa os passos que devem ser executados. Toda vez que uma função é chamada ela é colocada na pilha, quando a função retorna ou termina, ela é retirada da pilha. O Python mantém na pilha o nome da função e a linha em que ela foi chamada, e assim consegue voltar ao ponto anterior e continuar a execução de código.
As funções recursivas utilizam este mecanismo para conseguir retornar informações para elas mesmas.
Calculando fatorial em python com recursão
O exemplo mais simples de recursão é o calculo do fatorial. Para quem esqueceu das aulas de matemática, o fatorial de um numero corresponde ao produto de todos os inteiros consecutivos até um dado número. Então o fatorial de 5 é composto por:
5 x 4 x 3 x 2 x 1 = 120Com um laço for em python o código ficaria assim:
def fatorial(numero):
resultado = 1
for i in range(1, 6):
resultado = resultado * i
return resultadoUtilizando recursão o código fica assim:
def fatorial(numero):
if numero == 1:
return 1
return numero * fatorial(numero - 1)Muito mais elegante, não? Vamos entender o que está acontecendo. O primeiro if é o caso base, sem ele a função seria executada eternamente. A segunda parte é que realmente faz o cálculo. Vamos entender o que acontece na função se passarmos o valor 5 para ela:
Cada chamada vai adicionando uma chamada na pilha até que ele recebe a operação return. Neste momento a pilha começa a voltar e ser esvaziada. Veja o que acontece com a pilha de execução:
E para que mais serve? Bem, a recursão é muito usada para navegar em árvores, mas isto é um assunto para outro post. Hoje vamos ver uma aplicação prática de recursão para imprimir todo o conteúdo de uma pasta que afinal de contas é representado como uma árvore no sistema operacional.
Exemplo de recursividade em python: navegar em um sistema de arquivos
No post trabalhando com arquivos em python vimos como ler e escrever em arquivos e falamos brevemente do módulo os.path. Agora vamos usar outras funções deste módulo para listar arquivos.
Primeiro passo é criar uma função escanear pastas para imprimir todos os arquivos de uma pasta:
import os
def escanear_pastas(pasta_inicial):
arquivos = os.listdir(pasta_inicial)
for arquivo in arquivos:
print(arquivo)A função os.listdir(caminho) retorna uma lista do arquivos e diretórios contidos no caminho informado. Veja um exemplo do resultado desta execução:
Resultados para c:\Engenharia de Software
01 - Análise de Requisitos
02 - Modelagem de Classes
03 - Arquitetura
04 - Análise & Design
05 - Qualidade
06 - RUP
07 - Metodologia de Pesquisa
08 - SOA
09 - BPM
10 - Modelagem de Componentes
11 - Gerencia de Configuração e Mudanças
12 - Metricas
13 - Gerência de Projetos
14 - SOA Extension - SOA
15 - SOA Extension - BPM
16 - SOA Extension - Analise e Design
TCCAdicionando a função recursiva
Queremos navegar em todos os diretórios deste caminho e imprimir o nome de todos os arquivos presentes. E é aqui que começa a recursão. Em vez de apenas fazer um print dos arquivos encontrados na primeira pasta, vamos chamar a função escanear_pastas para cada um dos arquivos encontrados.
def escanear_pastas(pasta_inicial, pasta = ''):
arquivos = os.listdir(os.path.join(pasta_inicial, pasta))
for arquivo in arquivos:
print(arquivo)
escanear_pastas2(pasta_inicial, arquivo)Veja que criamos um novo parâmetro pasta na função. Este parâmetro se refere a pasta que queremos analisar. Precisamos adicionar ele pois ainda necessitaremos do caminho inicial pedido que está contido no parâmetro pasta_inicial. Como vimos no resultado, a função listdir apenas retorna o nome dos arquivos e pastas e não retorna o caminho completo. E para listar o conteúdo de um diretório necessitamos do caminho completo. Então o caminho inicial vai ficar guardado no parâmetro pasta_inicial e o caminho que estamos analisando será enviado no parâmetro pasta.
Note a declaração do parâmetro: pasta = ”. Esta é a maneira de definir um parâmetro como opcional no python, ele passa a ser opcional pois ele recebe um valor default. Ou seja, se não for passado este parâmetro, ele utiliza o valor default definido pela função. Utilizamos este mecanismo pois a primeira chamada desta função não precisa deste parâmetro.
Utilizamos também a função os.path.join para unir duas strings e formar um caminho. É importante a utilização desta função para não haver erros na hora de concatenar caminhos de arquivo, é a maneira mais segura de fazer.
pasta_inicial = 'c:\Engenharia de Software'
pasta = '01 - Análise de Requisitos'
print(os.path.join(pasta_inicial, pasta))
# c:\Engenharia de Software\01 - Análise de RequisitosPorém se executarmos este código com uma pasta de arquivos que contém varios níveis de pastas e arquivos vamos receber o seguinte erro:
C:\dev\python_testing> & C:/Python37/python.exe c:/dev/python_testing/recursao.py
01 - Análise de Requisitos
Análise de Requisitos - Aula 1.ppt
Traceback (most recent call last):
File "c:/dev/python_testing/recursao.py", line 42, in <module>
main(sys.argv[1:])
File "c:/dev/python_testing/recursao.py", line 5, in main
escanear_pastas2('D:\Roger\OneDrive\Documentos\Engenharia de Software')
File "c:/dev/python_testing/recursao.py", line 29, in escanear_pastas2
escanear_pastas2(pasta_inicial, arquivo)
File "c:/dev/python_testing/recursao.py", line 29, in escanear_pastas2
escanear_pastas2(pasta_inicial, arquivo)
File "c:/dev/python_testing/recursao.py", line 25, in escanear_pastas2
arquivos = os.listdir(os.path.join(pasta_inicial, pasta))
FileNotFoundError: [WinError 3] O sistema não pode encontrar o caminho especificado: 'D:\\Engenharia de Software\\Análise de Requisitos - Aula 1.ppt'Este erro acontece por que estamos tentando tratar um arquivo como se ele fosse um diretório. O erro acontece na função listdir(). Ocorre por que ainda não colocamos nosso caso base, que tem por objetivo sair da pilha de recursão. Neste caso o que queremos fazer é parar caso a pasta fornecida não seja uma pasta.
if not os.path.isdir(os.path.join(pasta_inicial, pasta)):
returnA função os.path.isdir() retorna True se o caminho passado é uma pasta. Já temos um código funcional, ele imprime todos os arquivos e pastas contidos na pasta base, mas gostaria de fazer uma última melhoria para poder visualizar o resultado melhor. Vamos inserir tabulações no print para poder ver a estrutura de pastas.
Portanto vamos usar um truque do Python muito legal, que é o multiplicador de string. É simples, se você quer repetir o mesmo caractere na tela varias vezes, basta multiplicá-lo pelo numero que deseja:
print("a" * 3)
# aaaVeja como fica a versão final da função:
def escanear_pastas(pasta_inicial, pasta = '', nivel = 0):
if not os.path.isdir(os.path.join(pasta_inicial, pasta)):
return
arquivos = os.listdir(os.path.join(pasta_inicial, pasta))
for arquivo in arquivos:
print('\t'*nivel, '>', arquivo)
escanear_pastas(os.path.join(pasta_inicial, pasta), arquivo, nivel + 1)Utilizamos o parâmetro nivel para indicar em que nivel de diretorio estamos, começamos do zero. Cada vez que chamamos a recursão enviamos o valor do nível atual + 1. E ao imprimir os arquivos, multiplicamos o caractere ‘\t’ (que é o código para tabulação) pelo nível atual.
Veja um exemplo do output completo:
> 01 - Análise de Requisitos
> Análise de Requisitos - Aula 1.ppt
> Análise de Requisitos - Aula 2.ppt
> Análise de Requisitos - Aula 3.ppt
> Pontos de Função.pdf
> TVX
> Diagramas - Professor
> browser.jar
> cat453964430134
> cat453964430134.htm
> contents.cnt
> dgm45396461028b.htm
> dgm45396461028b.png
> 02 - Modelagem de Classes
> Modelagem de Classes - Aula 1.pdf
> Modelagem de Classes - Aula 1b.pdf
> Modelagem de Classes - Aula 2.pdf
> Modelagem de Classes - Aula 2b.pdf
> Modelagem de Classes - Aula 3.pdf
> Modelagem de Classes - Aula 3b.pdf
> TVX
> Estudo de Caso - TVX V.3.0.doc