aula14 recursao

Prévia do material em texto

11/7/17
1
Recursão
Fundamentos	da	Programação	de	Computadores	– SME0332
Afonso	Paiva
apneto@icmc.usp.br
Recursão
• É um método de resolução de problemas que envolve
quebrar um problema em sub-problemas menores e
menores até chegar a um problema pequeno o suficiente para
que ele possa ser resolvido trivialmente.
• Recursão envolve uma função que chama a si mesma.
• Semelhante à prova de teoremas por indução
– Caso básico: O teorema	é verdadeiro trivialmente
– Caso geral: são provados assumindo que todos os casos mais
simples também são verdadeiros
11/7/17
2
Função Recursiva
• Implementa um algoritmo recursivo onde a solução dos
casos genéricos requerem chamadas	à própria função
• Uma função recursiva	é a maneira mais direta (mas não
necessariamente a melhor) de se resolver problemas de
natureza recursiva ou para implementar estruturas de
dados recursivas
• Uma função recursiva nos permite escrever soluções
elegantes para problemas que, de outra forma, podem
ser muito difíceis de programar.
Exemplo:	soma	de	uma lista de	números
def soma(lista):
res = 0
for x in lista:
res += x
return res
print(soma([1,3,5,7,9]))
• Matematicamente, a função acima calcula tal expressão
da seguinte forma:
((((1 + 3) + 5) + 7) + 9)
• Poderíamos colocar os parênteses na ordeminversa:
(1 + (3 + (5 + (7 + 9))))
11/7/17
3
(1 + (3 + (5 + (7 + 9))))
• Como usar essa soma para definir uma função recursiva
em Python?
Exemplo:	soma	de	uma lista de	números
• Note que a expressão acima pode ser escrita como:
soma	= primeiro elemento da	lista + resto da	lista
Exemplo:	soma	de	uma lista de	números
def soma(lista):
if len(lista) == 1:
return lista[0]
else:
return lista[0] + soma(lista[1:])
print(soma([1,3,5,7,9]))
11/7/17
4
Chamadas Recursivas
soma([1,3,5,7,9]) = 1 +
soma([3,5,7,9]) = 3 +
soma([5,7,9]) = 5 +
soma([7,9]) = 7 +
soma([9]) = 9
Cada vez que fazemos uma
chamada recursiva estamos
resolvendo um problema
menor, até chegar ao ponto
em que o problema não
pode ser mais simplificado.
Chamadas Recursivas
25 = soma([1,3,5,7,9]) = 1 + 24
soma([3,5,7,9]) = 3 + 21
soma([5,7,9]) = 5 + 16
soma([7,9]) = 7 + 9
soma([9]) = 9
No fim do processo cada
operação de adição é
calculada a medida que a
função soma percorre o
seu caminho reverso
através de uma série de
chamadas recursivas.
Quando soma retorna do
problema mais alto,
obtemos a solução para
todo o problema.
11/7/17
5
As	3	Leis	da	Recursão
1. Um algoritmo recursivo deve ter um caso básico (critério
de parada)
2. Um algoritmo recursivo deve mudar o seu estado e se
aproximar do caso básico
3. Um algoritmo recursivo deve chamar a si mesmo,
recursivamente
Vamos olhar para cada uma dessas leis com mais detalhes e
ver como elas foramutilizadas no algoritmo soma.
Exemplo:	soma	de	uma lista de	números
def soma(lista):
if len(lista) == 1:
return lista[0]
else:
return lista[0] + soma(lista[1:])
print(soma([1,3,5,7,9]))
1a Lei: um caso básico é a condição que permite que o
algoritmo recursivo pare de recorrer. Um caso básico é
tipicamente um problema que é suficientemente pequeno
para resolver diretamente (por exemplo, verificar o
tamanho de uma lista).
11/7/17
6
Exemplo:	soma	de	uma lista de	números
def soma(lista):
if len(lista) == 1:
return lista[0]
else:
return lista[0] + soma(lista[1:])
print(soma([1,3,5,7,9]))
2a Lei: a mudança de estado significa que alguns dados
utilizados pelo algoritmo são modificados. Normalmente,
os dados que representam o problema são reduzidos de
alguma forma. Como o caso básico é uma lista de
comprimento 1, uma progressão natural para o caso
básicoé encurtar a lista.
Exemplo:	soma	de	uma lista de	números
def soma(lista):
if len(lista) == 1:
return lista[0]
else:
return lista[0] + soma(lista[1:])
print(soma([1,3,5,7,9]))
3a Lei: é que o algoritmo deve chamar a si mesmo, ou seja,
a própria definiçãode recursão.
11/7/17
7
RecorrênciaNatural
• As vezes, alguns problemas possuem uma natureza
recursiva, ou seja, apresentam uma recursividade
pela sua própria definição.
• Exemplos:
– Sequência de Fibonacci
– Fatorial de um número
– Busca binária em uma lista ordenada
Exemplo: sequência de Fibonacci
def fib(n):
"Calcula o n-esimo termo da sequência de Fibonacci"
if n == 1: 
return 0
elif n == 2: 
return 1 
else:
return fib(n-1) + fib(n-2)
for i in range(1,11):
print(fib(i))
11/7/17
8
Exemplo: fatorial de um número
def fat(n):
"Calcula o fatorial de n"
if n == 0: 
return 1
else:
return n*fat(n-1)
print(fat(4))
Exemplo: busca binária
def teste(lista,valor):
def busca_bin(imin,imax):
if imin == imax:
return imin
else:
meio = round((imin + imax)/2)
if valor > lista[meio]:
return busca_bin(meio+1,imax)
else:
return busca_bin(imin,meio)
idx = busca_bin(0,len(lista)-1)
if valor == lista[idx]:
print(valor,'encontrado na posição',idx)
else:
print(valor,'não encontrado')
teste([1,2,5,6,9,12], 3)
11/7/17
9
Recursão Infinita
def recursiva(x):
if x == 0:
return True
else: 
return recursiva(x)
print(recursiva(1))
• Assim como nos casos dos laços de repegção,	é preciso
cuidado para não escrever funções infinitamente
recursivas
Traceback (most recent call last):
RecursionError: maximum recursion depth exceeded in comparison
Eficiência de	Funções Recursivas
• Quando uma função	é chamada, um pouco de memória	
é usado para guardar o ponto de retorno (backtracking),
os argumentos e variáveis locais
• Assim, soluções iterativas são normalmente mais
eficientes do que soluções recursivas equivalentes
• Isto não quer dizer que soluções iterativas sempre sejam
preferíveis a soluções recursivas
• Se o problema	 é recursivo por natureza, uma solução
recursiva	 é mais clara, mais fácil de programar e,
frequentemente, mais eficiente
11/7/17
10
Pensandode	Forma	Recursiva
• Ao invés de pensar construtivamente para para obter
uma solução, às vezes	é mais simples pensar em termos
de uma prova indutiva
• Considere o problema de testar se uma lista A	 é uma
permutação da lista B
– Caso básico: A éuma lista vazia
• Então A é permutação de B, seB também	é uma lista vazia
– Caso básico: A[0] não apareceem B
• Então A não	é uma permutação deB
– Caso geral: A[0]apareceem B na posição i
• Então A é permutação de B, seA[1:]é uma permutação deB\B[i]
Exemplo: testa permutações
def eh_permutacao(A,B):
"Retorna True se A é uma permutação de B"
if len(A) == 0:
return len(B) == 0
if A[0] in B:
i = B.index(A[0])
return eh_permutacao(A[1:],B[:i] + B[i+1:])
return False
print(eh_permutacao([1,2,3], [2,3,1]))
print(eh_permutacao([1,2,3], [2,3,1,1]))
11/7/17
11
EncontrandoRecursividade
• Alguns problemas não se apresentam naturalmente
como recursivos, mas pensar recursivamente fornece a
solução
• Tome o problema de computar todas as permutações de
uma lista L
– Assumamos que sabemos computar todas as permutações de
uma lista sem seu primeiro elemento L[0]
• Seja P uma dessas permutacõ̧es
• Então, a solução do global contém todas as listas obtidas inserindo L[0]
em todas as possíveis posições deP
Exemplo: calcular todas permutações
def permutacoes(lista):
if len(lista) == 1:
return [lista]
primeiro = lista[0]
resto = lista [1:]
resp = []
for P in permutacoes(resto):
for i in range(len(P)+1):
resp += [P[:i] + [primeiro] + P[i:]]
return resp
print(permutacoes([1,2,3]))