2
fibonacci_cache = {}
def fibonacci(n):
    if n in fibonacci_cache:
        return fibonacci_cache[n]

    if n==1:
        value=1
    elif n==2:
        value=1
    elif n>2:
        value=fibonacci(n-1) + fibonacci(n-2)

fibonacci_cache[n]=value
return value

for n in (1,1000,91723):
    print (n,":",fibonacci(n))

Versão do python:Python 2.7.10.

Devolveu-me este erro: RuntimeError: maximum recursion depth exceeded.

Como faço para resolver este problema?

4
  • 1
    O Python, por padrão, permite uma profundidade máxima de 1000 na recursividade. Você realmente precisa calcular para valores tão altos assim ou é um exercício para treino?
    – Woss
    Commented 7/11/2017 às 19:13
  • Eu pensava que dava para calcular para todos os números mas fui testar e devolveu isso.Eu quero alterar o código de forma a funcionar para qualquer numero Commented 7/11/2017 às 19:22
  • Recursivamente não será possível. Sempre haverá valores que estourarão a profundidade máxima da recursividade.
    – Woss
    Commented 7/11/2017 às 19:25
  • Como faço para alocar mais recursos para acelerar o calculo da expressão de fibonacci? Tipo o cpu tem quase 85% de inactividade e ele so esta a usar 10% para a execução do código Commented 7/11/2017 às 19:38

1 Resposta 1

1

Python, por padrão, permite você possuir uma profundidade máxima igual a 1000 dentro da recursividade; quando este valor é excedido, o erro citado será emitido.

RuntimeError: maximum recursion depth exceeded.

Você pode verificar o valor exato em seu servidor através da biblioteca sys, com a função getrecursionlimit:

import sys
print(sys.getrecursionlimit())

Você pode, ainda, alterar este valor com a função setrecursionlimit:

sys.setrecursionlimit(2000)

O valor máximo, conforme a documentação, que você pode definir dependerá das limitações plataforma onde está executando o código; e mesmo que seja um valor muito alto, sempre haverá um valor que excederá a profundidade máxima. Não há como fugir disso com recursividade.

Porém, uma solução bastante simples é calcular a sequência de Fibonacci através de um gerador:

def fibonacci(n):
    a, b = 1, 1
    yield a
    for _ in range(1, n):
        a, b = b, a+b
        yield a

Mas como você não tem interesse em obter a sequência propriamente dita, mas sim o n-ésimo termo da sequência, podemos gerar um iterador que percorrerá nosso gerador no intervalo que desejamos, isto é, no n-ésimo termo. Fazemos isso utilizando a função islice da biblioteca itertools:

import itertools

def nth_value(n):
    iterator = itertools.islice(fibonacci(n), n-1, None)
    return next(iterator)

Ficando:

import itertools

def fibonacci(n):
    a, b = 1, 1
    yield a
    for _ in range(1, n):
        a, b = b, a+b
        yield a

def nth_value(n):
    return next(itertools.islice(fibonacci(n), n-1, n))

Veja funcionando no Ideone | Repl.it | Wolfram Alpha

8
  • Tentei executar isso na minha maquina mas ele demora muito a obter o valor. Não tem forma de diminuir o tempo de execução? no site ele devolve o resultado mais rápido. Se calhar o poder computacional não pode ser equiparado. Commented 7/11/2017 às 20:20
  • @ManuelJose Sim, esta solução tende a ser muito rápida. Tem certeza que implementou o código corretamente?
    – Woss
    Commented 7/11/2017 às 20:24
  • como faço para ver o tempo de execução. Se os tempos de execução forem diferentes no site repl.it/NuZ5 e na minha maquina, quer dizer que temos diferentes poderes computacionais, nomeadamente na rapidez em carregar valores da memória ram para o cpu Commented 7/11/2017 às 20:30
  • @ManuelJose Com o comando time no Linux, ou com o módulo timeit do Python.
    – Woss
    Commented 7/11/2017 às 20:37
  • Na maquina é ligeiramente mais rápido que no site. Mas os valores não são sempre constantes a cada execução Commented 7/11/2017 às 21:11

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

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .