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.

`NameError: name 'n' is not defined` your code doesn't even run... — LtWorf, Dec 09 '18 at 00:01
`def fib2(int:n):` is not a valid type hint, the order is wrong. If I switch them I get the correct answer and no error. — Andras Deak -- Слава Україні, Dec 09 '18 at 00:02

Óscar López · Accepted Answer · 2018-12-09T00:22:02.610

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

edited Dec 09 '18 at 00:22

answered Dec 09 '18 at 00:00

Óscar López

232,561
37
312
386

it works, but why the typing hint is wrong? `F:List = [-1] * 50` – AbstProcDo Dec 09 '18 at 00:19
1

You can fix the type hint for the list `F` by using a lowercase l: `F:list = [-1] * 50` – tel Dec 09 '18 at 00:21
@JawSaw it's not only the array declaration, the function parameter was incorrect. Take a closer look. – Óscar López Dec 09 '18 at 00:23

score 1 · Answer 2 · answered Dec 09 '18 at 00:18

The problem lies in your type hint: it should be n: int instead of int: n.

In a normal script, you would get a NameError as here:

def fib2(int: n):
    pass

---------------------------------------------------------------------------

NameError                                 Traceback (most recent call last)
<ipython-input-19-2a2734193e18> in <module>()
----> 1 def fib2(int: n):
      2     pass

NameError: name 'n' is not defined

What happens in your case is that you probably have n defined in one of the cells you've run before in IPython. So, you don't get a 'NameError', but your parameter gets the name int, and the n used in the function is the global n you used somewhere before. If it is a number greater than 2, your recursive calls will never end:

n = 3  # might have been in some other cell

F = [-1] * 101

def fib2(int: n):

    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(100))
---------------------------------------------------------------------------

[...]

RuntimeError: maximum recursion depth exceeded in comparison

Just write the type hint in the right order and everything is fine:

F = [-1] * 101

def fib2(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(100))
# 354224848179261915075

score 0 · Answer 3 · 2018-12-10T15:16:32.823

Try this:

fib_aux = [-1] * 50
def fib(n):
    if n < 2:
        return n
    else:
        if fib_aux[n] < 0:
            fib_aux[n] = fib(n - 1) + fib(n - 2)
        return fib_aux[n]

With a list, you can also do this to avoid recursion:

fib_aux = [0, 1]
def fib(n):
    m = len(fib_aux)
    for i in range(m, n + 1):
        fib_aux.append(fib_aux[i - 1] + fib_aux[i - 2])
    return fib_aux[n]

Rather than managing a list, you can use a general memoization function:

def memoize(f):
    h = {}
    def g(*arg):
        if arg not in h:
            h[arg] = f(*arg)
        return h[arg]
    return g

@memoize
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

See this question for more informations about Python decorators (@).

Note that the first and last method can fail due to recursion limit. The second solution does not use recursion. However, if you need only a few values of fib(n) for large n, there are faster solutions using argument doubling (see this on Math.SE).

Fibonacci in a cached solution

3 Answers3