Nth Fibonacci in python

def fibonaci(i,memo):
    if i == 0 or i == 1:
       return i

    if memo[i]==-1:
       memo[i] = fibonaci(i-1,memo) + fibonaci(i-2,memo)

    return memo[i]

def fibo(n):
    a = []
    return fibonaci(n,a)

print(fibo(2))

I’m a Java programmer learning python. This algorithm computes the nth fibonacci number using recursion + memoization. I don’t understand why I’m seeing this error “IndexError: list index out of range” when running the program in python. Can anybody help? Thanks a ton!

Answer

I made few changes in your code to get nth Fibonacci no.(there might be other way too)

def fibonaci(i,memo):
    if i == 0 or i == 1:
       return i

    if memo[i] == -1:
       memo[i] = fibonaci(i-1,memo) + fibonaci(i-2,memo)

    return memo[i]

def fibo(n):
    a = [-1] * n
    return fibonaci(n-1,a)

print(fibo(5))
print(fibo(10))
print(fibo(13))
print(fibo(57))

And output is :-

3
34
144
225851433717