Issue with Recursive Algorithm

[nolanmaris]

Hello,

I am currently working on a project where I need to calculate Fibonacci numbers using a recursive algorithm implemented in Python. My function works perfectly for small values of n; but I run into a RecursionError: maximum recursion depth exceeded when trying to compute Fibonacci numbers for larger inputs; such as Fibonacci(100).

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

While this approach is straightforward; it becomes highly inefficient for larger values of n due to the excessive number of redundant computations. For example; Fibonacci(10) results in 177 function calls; and this grows exponentially with the input size.
I’ve read that recursion for problems like this can lead to deep call stacks and is generally inefficient due to recalculating the same values multiple times. T

I understand that memoization can help by storing previously computed values to avoid redundant calculations. However; I’m unsure about the best way to implement this in my current setup. Could someone provide guidance or examples on how to integrate memoization with a recursive approach?
I’ve also heard that iterative solutions might be more efficient for this problem. I’m interested in learning about iterative methods that could replace the recursive solution; along with any performance improvements I might expect.


I’ve read that tail recursion can sometimes be optimized by compilers to avoid deep call stacks. Is this applicable in Python; and if so, how can I modify my function to use tail recursion? I have referred Python Documentation - functools.lru_cache



I’d greatly appreciate any advice; code examples / references to resources that could help me address these issues and improve the efficiency of my Fibonacci calculation.



Thank you in advance for your assistance!

[Baltuilhe]

You can use any of the solutions below:

Code: Select all

known = {0:0, 1:1}
def fibonacci(n):
    assert(n >= 0), 'n must be >= 0'
    if n in known:
        return known[n]
    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res

Or:

Code: Select all

def fib2(n):
    if n == 1 or n == 2:
        return 1
    fib_1 = 1
    fib_2 = 1
    while n > 2:
        tmp = fib_2
        fib_2 = fib_2 + fib_1
        fib_1 = tmp
        n -= 1
    return fib_2