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

Tem muito a ver com provas de indução em matematica.

Prova por indução

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}

Recursão

um exemplo bobo: fatorial

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

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
    

Um exemplo não bobo: permutacoes

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.

Ordenação

como o sorted funciona?

ordenação ingenua

dado uma lista

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)

Sort recursivo: mergesort

A ideia do mergesort é dividir a lista em 2

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)

Outro sort recursivo: quicksort

a ideia do quick sort é “magicamente/com sorte” descobrir o valor do meio da lista (nao na posicao do meio mas o valor mediano)

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