Fibonacci in a cached solution

Question

I learned a memorized solution to fibonacci in c++ as

#include<iostream>
using namespace std;
int F[51];

int fib(int n) {
    if (n<=1)
    {
        return n;
    }
    if (F[n] != -1)
    {
        return F[n];
    }
    F[n] =  fib(n-1) + fib(n-2);
    return F[n];
}

int main()
{   
    for (int i=0; i<51; i++)
    {
        F[i] = -1;
    }
    int n;
    cout<<"Give me an n: ";
    cin>>n;
    int result = fib(n);
    cout<<result;
}

It worked correctly,

$ g++ fibonacci.cpp 
$ ./a.out
Give me an n: 10
55

Try to reproduce it with python

In [2]: %paste                                                                                                        
F:List = [-1] * 50

def fib2(int:n) -> int:

    if n < 2:
        return n
    if F[n] != -1:
        return F[n]
    F[n] =  fib2(n-1) + fib2(n-2)
    return F[n]

print(fib2(10))

Nevertheless, it report RecursionError: maximum recursion depth exceeded in comparison

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-2-5e5ce2f4b1ad> in <module>
     10     return F[n]
     11 
---> 12 print(fib2(10))

<ipython-input-2-5e5ce2f4b1ad> in fib2(int)
      7     if F[n] != -1:
      8         return F[n]
----> 9     F[n] =  fib2(n-1) + fib2(n-2)
     10     return F[n]
     11 

... last 1 frames repeated, from the frame below ...

<ipython-input-2-5e5ce2f4b1ad> in fib2(int)
      7     if F[n] != -1:
      8         return F[n]
----> 9     F[n] =  fib2(n-1) + fib2(n-2)
     10    

Double checked that the python solution has the identical logic with the proceeding solution.

What's the problem with my codes.

Answer 1

Type hints were incorrect, this works for me:

# fixed type hint
F:list = [-1] * 50

# fixed type hint
def fib2(n:int) -> int:
    if n < 2:
        return n
    if F[n] != -1:
        return F[n]
    F[n] = fib2(n-1) + fib2(n-2)
    return F[n]

fib2(49)
=> 7778742049