I am trying to find the last digit of Big Fibonacci numbers, my script can count them and find the last digit fast but when I try to compute numbers from 1000 I get RecursionError.

Here is my scrip:

cache = {}

def last_digit_of_fibonacci_number(n):
    assert 0 <= n <= 10 ** 7

    if n in cache:
        return cache[n]

    if n == 1 or n == 2:
        return 1
    elif n == 0:
        return 0
    else:
        result = (last_digit_of_fibonacci_number(n - 1)   last_digit_of_fibonacci_number(n - 2)) % 10
        cache[n] = result
        return result

any ideas of how to fix my issue without resetting the recursion limit using setrecursionlimit()?

CodePudding user response：

Note that since you are only interested in the last digit of each Fibonacci number, the sequence of results is cyclic: As soon as there are two subsequent results that equal two previous subsequent results, the values repeat.

For example, the results for 1 and 2 are both 1, so as soon as two subsequent later return values are also both 1, we have a cycle. Let's find these cycles:

last_digit_of_fibonacci_number(250)

for n in range(3, 250):
    if cache[n] == cache[n   1] == 1:
        print(n)

61
121
181
241

So the length of this cycle is 60, and you can alter your function to exploit this fact:

cache = {}

def last_digit_of_fibonacci_number(n):
    assert 0 <= n <= 10 ** 7

    if n in cache:
        return cache[n]
    if n == 1 or n == 2:
        return 1
    if n == 0:
        return 0
    
    if n > 61:
        n = n % 60
        
    result = (last_digit_of_fibonacci_number(n - 1) 
                last_digit_of_fibonacci_number(n - 2)) % 10
    cache[n] = result
    return result

Since the cycle length is smaller than the recursion limit, this will avoid any recursion depth problems.