3

Eu criei um algoritmo recursivo para contar o numero de vezes que um certo numero n aparece numa lista ls. Parecia funcionar se a lista ls é bastante pequena (entre 10 e 100), mas se é grande, tipo 1000, parece não funcionar mais: entra numa recursão infinita...

Alguém consegue perceber porquê?

def _count(n, ls, index):
    if index < len(ls):
        if ls[index] == n:
            return 1 + _count(n, ls, index + 1)
        else:
            return _count(n, ls, index + 1)
    return 0


def count(n, ls):
    """Counts how many times n appears in the list or tuple ls."""
    return _count(n, ls, 0)


if __name__ == "__main__":
    from random import randint

    for i in range(10):
        ls = [randint(0, 10) for _ in range(1000)]  # modifica 1000 para 100 para funcionar
        print("List:", ls)

        r = randint(0, 10)
        print("Counting number:", r)

        c = count(r, ls)
        print("Counted:", c)

        if c != ls.count(r):
            raise Exception("Something is wrong with the implementation of count...!")

1 Resposta 1

1

Na maioria das linguagens de programação, cada chamada de função precisa de alguns bytes da pilha de execução e em geral existe um limite máximo para o tamanho da pilha. Num computador de Desktop hoje em dia esse limite normalmente é da ordem de centenas de milhares de chamadas mas em Python o limite é bem baixo de propósito:

> import sys
> sys.getrecursionlimit()
1000

Você pode aumentar um pouco o limite com sys.setrecursionlimit mas no fim das contas o ideal é usar um algoritmo com loop, que consuma uma quantidade constante de memória, ao invés do algoritmo recursivo, que consome uma quantidade de pilha diretamente proporcional ao tamanho da entrada. Em linguagens como Python é melhor usar algoritmos recursivos apenas quando o consumo máximo da pilha crescer mais devagar. Por exemplo, muitos em muitos algoritmos recursivos o tamanho máximo da pilha é proporcional ao logaritmo do tamanho da entrada.


Dito isso tudo, existem algumas linguagens de programação que garantem que chamadas recursivas em posição de cauda não gastam espaço adicional na pilha.

Uma linguagem que garante a otimização da recursão de cauda é Lua. Em Lua podemos escrever um algoritmo de count que nunca estoura a pilha.

function _count(x, xs, i, nfound)
    if i <= #xs then
        if xs[i] == x then
            return _count(x, xs, i+1, nfound+1)
        else
            return _count(x, xs, i+1, nfound)
        end
    else
        return nfound
    end
end

function count(x, xs)
    return _count(x, xs, 1, 0) -- Em Lua os índices começam em 1
end

Tive que alterar o seu algorítmo um pouco porque a chamada recursiva em 1 + _count(...) não está em posição de cauda. Mas o importante que eu queria mostrar é que em algumas linguagens é possível sim escrever algoritmos recursivos que não estouram a pilha.

1
  • O limite de recursão é para todas as funções do seu programa e isso inclui o main, a chamada para count, a chamada para len em index < len(xs), etc. Se você der sys.setrecursionlimit prum número pequenininho dá pra ver isso claramente.
    – hugomg
    Commented 1/01/2016 às 13:16

Você deve fazer log-in para responder a esta pergunta.