CODEWITHSUNDEEP
pythonrecursionmemory-efficient
Jacobiman
Jacobiman

Reputation: 155

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

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!

Upvotes: 2

Views: 540

Answers (3)

Serafim
Serafim

Reputation: 534

In the task they give a recursive definition of the fibonacci sequence but nothing is said about a recursive implementation. This is an iterative implementation of the recursive definition:

def fib(n):
    if n == 0:
        return 0
    f1, f2 = 0, 1
    for i in range(1, n + 1):
        f1, f2 = f2, f1 + f2
    return f2

Upvotes: 0

alani
alani

Reputation: 13079

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.)

Upvotes: 2

M Z
M Z

Reputation: 4799

With a recursive implementation, you will almost end up with trouble when trying to go to such great depths. Like @alaniwi stated, you can always implement it in a non-recursive method. Here's a O(n) time solution with a O(1) space complexity. (Note: Theoretically you can even get a O(log n) solution.)

from collections import deque

def fib(n):
    past = deque([1], maxlen=2)
    for _ in range(n): past.appendleft(sum(past))
    return past[0]

Because the fibonacci function only requires the last two values of f, we can store only those and bubble upwards.

Upvotes: 0

Related Questions