from tabelas import printa_tabela

def recorrência_linear(valores_base,
                       coeficientes,
                       fun             = lambda _:0,
                       até             = 20,
                       printa          = True,
                       passo           = False,
                       linhas_externas = True,
                       prefixo         = '   '):
    """
    recorrência_linear([base_0,base_1,...,base_{k-1}],[a_1,a_2,...,a_k], até, printa, passo, linhas_externas)
    é a função dada pela recorrência

    n = 0   => F(n) = base_0
    n = 1   => F(n) = base_1
    ...
    n = k-1 => F(n) = base_{k-1}
    n >= k  => F(n) = [(a_1 * F(n-1)) + (a_2 * F(n-2)) + ... + (a_k * F(n-k))] + fun(n)

    Uma tabela com os resultados é impressa, se o argumento 'printa' for True;
    caso contrário, a lista [F(0), F(1), ..., F(até)] é retornada
    """
    assert len(coeficientes) == len(valores_base), "Forneça uma quantidade de casos bases igual à ordem da recorrência!"
    contagem = len(coeficientes)-1
    lista_n = []
    lista_F = []
    lista_razões = []
    for i,val in enumerate(valores_base):
        lista_n.append(i)
        lista_F.append(val)
        lista_razões.append("base")
    calculados = valores_base.copy()
    calculados = list(reversed(calculados))
    while contagem < até:
        val_antigo = calculados[0]
        contagem += 1
        val_novo = fun(contagem)
        for coef,val in zip(coeficientes,calculados):
            val_novo += coef*val
        calculados[0], calculados[1:] = val_novo, calculados[:-1]
        lista_n.append(contagem)
        lista_F.append(calculados[0])
        if val_antigo != 0:
            lista_razões.append(val_novo/val_antigo)
        else:
            lista_razões.append("-")
    if printa:
        printa_tabela(cabeçalho       = ["n","F(n)","Razão"],
                      colunas         = [lista_n,lista_F,lista_razões],
                      passo           = passo,
                      linhas_externas = linhas_externas,
                      prefixo         = prefixo)
        
    else:
        return lista_F