#2021 02 07 algoritmos recursivos

 #2021 02 07 algoritmos recursivos
def fatorial(n):
    if n < 1:        #base da recursao
        return 1
    else:
        return n * fatorial(n-1)    #chamada recursiva    
import pytest
@pytest.mark.parametrize("entra, sai",[
    (0, 1),
    (1, 1),
    (2, 2),
    (3, 6),
    (4, 24),
    (5, 120)
    ])
def testFat(entra, sai):
    assert fatorial(entra) == sai
def fibonacci(n):
    if n < 2:        #base da recursao
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)    #chamada recursiva    
@pytest.mark.parametrize("entra, sai",[
    (0, 0),
    (1, 1),
    (2, 1),
    (3, 2),
    (4, 3),
    (5, 5),
    (6, 8),
    (7, 13),
    (8, 21)
    ])
def testFibo(entra, sai):
    assert fibonacci(entra) == sai
def buscaBinaria(lista, elemento, min=0, max=None):
    if max == None:
        max = len(lista)-1 # testar o elemento como max
    if max < min:
        return False
    else:
        meio = min + (max-min)//2
    if lista[meio] > elemento:
        return buscaBinaria(lista, elemento, min, meio-1)
    elif lista[meio] < elemento:
        return buscaBinaria(lista, elemento, meio+1, max)
    else:
        return meio
a = [10,20,30,40,50,60]
@pytest.mark.parametrize('lista, valor, saida', [
    (a, 10, 0),
    (a, 20, 1),
    (a, 30, 2),
    (a, 40, 3),
    (a, 50, 4),
    (a, 60, 5),
    (a, 70, False),
    (a, 15, False),
    (a, -10, False)])
def testBin(lista, valor, saida):
    assert buscaBinaria(lista, valor) == saida
def mergeSort(lista):
    if len(lista) <= 1:        # Base da recursao
        return lista
    meio = len(lista) // 2
    esquerda = mergeSort(lista[:meio])
    direita = mergeSort(lista[meio:])
    return merge(esquerda, direita)
def merge(esquerda, direita):
    if not esquerda:
        return direita
    if not direita:
        return esquerda
    if esquerda[0] < direita[0]:
        return [esquerda[0]] + merge(esquerda[1:], direita)
    return [direita[0]] + merge(esquerda, direita[1:])
print(mergeSort([6,7,8,1,2,4,3,5]))