On Sun, Apr 3, 2022 at 2:46 PM Cecil Westerhof via Python-list <
python-list@python.org> wrote:
> Betty Hollinshead <lizzyhollin...@gmail.com> writes:
>
> > "Memoising" is the answer -- see "Python Algorithms" by Magnus Lie
> Hetland.
> > In the mean time, here a simplified version of "memoising" using a dict.
> > This version handles pretty large fibonacci numbers!
> >
> > # fibonacci sequence
> > # memoised - but using a simple dictionary (see Python Algorithms, p177)
> >
> > memo = {}
> > memo[1] = 1
> > memo[2] = 2
> >
> > def fib(n):
> > if n in memo:
> > return memo[n]
> > else:
> > memo[n] = fib(n - 1) + fib(n - 2)
> > return memo[n]
> >
> >
> > print(100, fib(100))
> > print(memo)
>
> No, it is not. It is the answer on a completely different question.
> Nice, but not what I was asking about. And there is even an error in
> the solution.
>
> By the way: it is better to do it iterative. Try (when not done a
> calculation before) fib(3_000).
>
I think I missed part of this conversation, but here is how I've done
fibonacci numbers in the past, using functools.lru_cache:
#!/usr/local/cpython-3.8/bin/python
"""Compute the first n numbers in the fibonacci sequence."""
import functools
import sys
@functools.lru_cache(maxsize=None) # pylint: disable=no-member
def find_recursive(number):
"""Find a Fibonacci number recursively - without the callstack
explosion."""
assert number >= 0
if number == 0:
return 0
if number == 1:
return 1
result = find_recursive(number - 1) + find_recursive(number - 2)
return result
def main():
"""Compute fibonacci numbers."""
top = 5000
if sys.argv[1:]:
top = int(sys.argv[1])
if sys.argv[2:]:
sys.stderr.write('Usage: {} 5000\n'.format(sys.argv[0]))
sys.exit(1)
for number in range(1, top + 1):
print(number, find_recursive(number))
main()
--
https://mail.python.org/mailman/listinfo/python-list
