How to avoid memory error when using recursion? (Fibonacci Numbers)

Question

I have the following exercise:

'''FIBONACCI

   Compute the n'th Fibonacci number fib(n), defined recursively:

      fib(0) == 0, fib(1) == 1, fib(n) = fib(n - 1) + fib(n - 2)

   Input:

      A single line containing an integer n, 0 <= n <= 10.000

   Output:

      A single line with the integer fib(n).

   Example:

     Input:   10

     Output:  55
'''

My raw attempt so to speak:

def fib(n):
    if n <= 1:
        return n
    if n >= 2:
        return fib(n-1) + fib(n-2)
    
n = int(input())  # Read integer n from standard input
print(fib(n))

However this code can only handle up to around n = 500 before reaching maximum recursion depth. To increase that number and create code that can handle up to 10 000, I have tried two things: 1) To increase maximum recursion depth and 2) To use memoization in the form of a decorator. Now the code can handle up to about n = 2000:

import sys
from functools import lru_cache

sys.setrecursionlimit(10000)

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    if n >= 2:
        return fib(n-1) + fib(n-2)

n = int(input())  # Read integer n from standard input
print(fib(n))

With n > 2000 I get an memory error (stack overflow). How do I fix this? What more can I do? Is it even possible with my recursive function or do I have to change it in some way to make it work? Any help is appreciated!

Answer 1

A simple implementation of the nth Fibonacci number. There is no need to use recursion.

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        fa, fb = 0, 1
        for i in range(2, n + 1):
            fa, fb = fb, fa + fb
        return fb

(Note: this is not the fastest. It is O(n). An O(log n) solution is available -- e.g. here, see their method 5.)