1

Even with memoization I can not calculate the fibonacci (1000). This is my code (its same as a textbook example on memoization).

inputnumber = 10000 # the error starts if n > 998
existingvalues = {}

def fib_series(n):
    if(n <= 1):
        return n
    else:
        if(n in existingvalues):
            value = existingvalues[n]
        else:
            value = fib_series(n-1) + fib_series(n-2)
            existingvalues[n] = value
        return value

the error I get:

Traceback (most recent call last):
  File "C:/PycharmProjects/learnpy/11 - recursion.py", line 24, in <module>
    print(fib_series(inputnumber))
  File "C:/PycharmProjects/learnpy/11 - recursion.py", line 18, in fib_series
    value = fib_series(n-1) + fib_series(n-2)
  File "C:/PycharmProjects/learnpy/11 - recursion.py", line 18, in fib_series
    value = fib_series(n-1) + fib_series(n-2)
  File "C:/PycharmProjects/learnpy/11 - recursion.py", line 18, in fib_series
    value = fib_series(n-1) + fib_series(n-2)
  [Previous line repeated 994 more times]
  File "C:/PycharmProjects/learnpy/11 - recursion.py", line 12, in fib_series
    if(n <= 1):
RecursionError: maximum recursion depth exceeded in comparison

The reason why I wanted to do this, is comparing the performance between recursion and iteration. the following code does the iteration and can find the fibonacci for n > 1000 in almost similar time.

def fib_series(i):
    a = 0
    b = 1
    c = 0
    count = 0
    while (count < i):
        c = a + b
        a = b
        b = c
        count = count + 1

    print(c)

Is there anything related to O(complexity) that I should consider while comparing these two technique of addition (recursion vs iteration)?

Arjee
  • 372
  • 3
  • 15
  • 1
    you can up your `sys.setrecursionlimit` that should enable you to push past 1k, but generally iterative approach should be better in python – user3012759 Sep 04 '17 at 15:41
  • 1
    That is one possibility (the most common, to be fair) to implement the Fibonacci sequence recursively, and it will be always worse because it has exponential complexity, while the iterative version is linear. However, you can have a recursive implementation with linear complexity too, [like this](https://stackoverflow.com/a/13826877/1782792). In a language with [tail call optimization](https://stackoverflow.com/q/310974/1782792) they would be equivalent, but Python is no such language, so you will also hit a limit anyway. – jdehesa Sep 04 '17 at 15:54
  • yes, it works. But after a certain increase in input range the recursion limit also does not work. Also the iterative approach seems better than recursive at least in this scenario. thanks @user3012759, @ jdehesa – Arjee Sep 04 '17 at 16:05

0 Answers0