MC-102 — Aula 16
Recursao
Oficialmente, recursão é a situação onde uma função chama ela propria. Mas é mais do que isso. É uma forma de resolver problemas
tenho que resolver um problema
para um valor “pequeno” é facil ou ridicuarmente facil resolve-lo
para resolver para um valor grande, voce assume que sabe resolve-lo para um problema menor, e decompoe o problema grande em problemas menores (que vc assumiu que sabe resover) e talvez tenha que combinar as respostas dos problemas menores para obter a responta do problema grande.
e isso funciona!!
Tem muito a ver com provas de indução em matematica.
prove que é verdade para um caso base
assuma que é verdade para n, e prove que isso implica que é verdade para n+1
exemplo
1+2+3+ \ldots +n = \frac{n(n+1)}{2}
1 = \frac{1(1+1)}{2}
1+2+3+ \ldots +n = \frac{n(n+1)}{2}
1+2+3+ \ldots +n+(n+1) = \frac{n(n+1)}{2} + (n+1)\\ = \frac{n(n+1)}{2} + \frac{2(n+1)}{2} \\ = \frac{n^2 + n + 2n + 2}{2}\\= \frac{n^2 + 3n +2}{2}\\= \frac{(n+1)(n+2)}{2}\\= \frac{(n+1)((n+1)+1)}{2}
Fatorial
0! = 1\\n! = n * (n-1)!
def fatorial(n):
if n==0:
return 1
else:
return n*fatorial(n-1)
ou de forma geral
def fatorial(n):
# base
if n==0:
return 1
quebra = n-1
rec = fatorial(quebra)
combina = n*rec
return combina
usando a ideia de
quebrar o problema grande em problemas menores (neste caso um so problema menor)
resolver os problemas menores
combinar os resultados dos problemas menores para obter a solucao do programa grande.
Fatorial é um exemplo bobo porque há uma solução simples usando interacao/for
def fatorial2(n):
if n==0:
return 1
prod=1.0
for x in range(1,n+1):
prod = prod*x
return prod
gere todas as permutaçoes de uma lista
pegue o 1o elmento da lista, gere todas as permutacoes da lista sem o primeiro, e grude o primeiro na frente dos resultados.
ai pegue o 1o elemento da lista. gere todas as permutacoes da lista sem o segundo elemento, e grude o primeiro na frente dos resultados.
caso base. Se a lista so tem um elemento so há uma permutacao, a propria lista
def permutacoes(lista):
if len(lista) <= 1:
return [lista]
else:
saida = []
for i in range(len(lista)):
first = lista[i]
remaining = lista[:i] + lista[i+1:]
for perm in permutations(remaining):
saida.append([first] + perm)
return saida
quando i=0
first = lista[i]
pega o primeiro elemento da lista
remaining = lista[:i] + lista[i+1:]
é a lista sem o primeiro
for perm in permutations(remaining):
é cada uma das permutações da lista sem o primeiro
[first] + perm
gruda o primiero na frente de cada permutacao (da recursao)
saida.append([first] + perm)
inclui isso na saida
e ai o i=1 e ele repete tudo para o segundo elemento da lista
Esse exemplo não é bobo. Na verdade usar recursão é (provavelmente) o unico jeito de resolver esse problema.
E ele fica simples com recursão.
como o sorted
funciona?
dado uma lista
procure o menor elemento da lista e coloque-o na primeira posicao (na verdade troque-o como o elemento na primeira posição)
procure o menor elemento no resto da lista (sem o primeiro) e coloque-o troque com o da 2a posiçao.
isso é chamado de selection sort
def selection_sort(data):
for i in range(len(data)):
# Acha a posição do menor a partir do i
min_index = i
for j in range(i + 1, len(data)):
if data[j] < data[min_index]:
min_index = j
# troca o i com o menor (a partir do i)
data[i], data[min_index] = data[min_index], data[i]
return data
Selection sort demora um tempo proporcional ao quadrado do tamanho da lista
def mklist(n):
import random
randlist = []
for i in range(n):
randlist.append(random.randint(0,5000)
return randlist
a = mklist(1000)
b = mklist(5000)
%timeit selection_sort(a)
%timeit selection_sort(b)
A ideia do mergesort é dividir a lista em 2
recursivamente ordenar as 2 sublistas
e misturar (merge
) as 2 sublistas ordenadas na lista
final ordenada
def merge_sort(data):
# caso base
if len(data) <= 1:
return data
# Divide a lista em 2 pedacos
mid = len(data) // 2
left = data[:mid]
right = data[mid:]
# ordena as 2 listas recursivamente
left_sorted = merge_sort(left)
right_sorted = merge_sort(right)
# mistura as duas listas ordenadas
return merge(left_sorted, right_sorted)
O merge
passeia pelas 2 listas ao mesmo tempo, pegando o
menor entre elas e colocando na saida, e avançando na lista que tinha o
menor. E se sobrar uma so lista ao final, coloque ela na saida.
def merge(left, right):
saida = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
saida.append(left[i]) # copia do left
i += 1 # anda no left
else:
saida.append(right[j]) # copia do right
j += 1
# gruda o que sobrou depois que uma lista acabou
saida += left[i:]
saida += right[j:]
return saida
O merge_sort
demora um tempo proporcional a n log(n) onde n é o tamanho da lista
%timeit merge_sort(a)
%timeit merge_sort(b)
a ideia do quick sort é “magicamente/com sorte” descobrir o valor do meio da lista (nao na posicao do meio mas o valor mediano)
coloque todos abaixo do meio numa lista, coloque todos acima numa outra lista
recursivamente ordene essas duas listas
apenas grude a listas ordenada dos pequenos e a lista ordenada dos grandes
Mas e esse “magicamente/com sorte”? Na verdade o quicksort assume que o primeiro elemento da lista é a mediana. Obviamente não é verdade mas na média nao faz muita diferença ( a prova é complicada)
Na media o tempo de execução do quicksort é tambem proporcional a n*log(n)
def quicksort(lista):
if len(lista)<=1:
return lista
meio = lista[0]
pequeno, grande = separa(lista, meio)
return quicksort(pequeno)+quicksort(grande)
ESTE CODIGO NAO ESTA 100% CERTO
NAO RODE
ESTE NAO É O QUICKSORT TRADICIONAL
def separa(lista,meio):
pequeno = []
grande = []
for x in lista:
if x <= meio:
pequeno.append(x)
else:
grande.append(x)
return pequeno, grande
ESTE CODIGO NAO ESTA 100% CERTO
NAO RODE
O quicksort tradicional nao usa 2 listas como no codigo acima, ele
rearanja os elementos de lista para que os pequenos estejam de um lado e
os grandes do outro. Tradicionalmente o separa
é bem
diferente