File: fib.py

package info (click to toggle)
python-memray 1.17.0%2Bdfsg-1
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid, trixie
  • size: 24,396 kB
  • sloc: python: 28,451; ansic: 16,507; sh: 10,586; cpp: 8,494; javascript: 1,474; makefile: 822; awk: 12
file content (27 lines) | stat: -rw-r--r-- 415 bytes parent folder | download 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
import sys


def fib1(n):
    my_list = [0, 1]
    for i in range(2, n + 1):
        my_list.append(my_list[i - 1] + my_list[i - 2])
    return my_list[-1]


def fib2(n, cache={0: 0, 1: 1}):
    if n in cache:
        return cache[n]
    cache[n] = fib2(n - 1) + fib2(n - 2)
    return cache[n]


def run():
    sys.setrecursionlimit(100000)
    n = 99900
    a = fib1(n)
    b = fib2(n)

    assert a == b


run()