# How to make this recursive function faster in Python or Java?

I have this recursive function: F(n)=4F(n-1)+F(n-2), for all n>=2, where F(0)=0 and F(1)=1. This is my code in python

```def f(n):
res = 0;
if n == 0:
return 0
elif n == 1:
return 1
else:
res=(4*(f(n-1)))+f(n-2)
return res

print f(2424)
```

And the method in Java:

```static public long f(int n){
long res = 0;
if(n==0){
return 0;
}else if(n==1){
return 1;
}else{
res=(4*(f(n-1)))+f(n-2);
}
return res;
}
```

I just call it in the main:

```public static void main(String[] args) {
}
```

I have to evaluate F(2424), but it takes so long that after 5 hours the program hasn’t finished. I was wondering if I am doing something wrong or if there is a better way to do this. I am open to other lenguajes like C, C++ or Mathematica. I know it works because with smaller numbers it gives the right answer. The answer for F(2424) is a really big number, it’s this:

12811645111887631525475128340409754383702010324654360624942154540228791340642173492088690105771256884654221447044702887147589907921153496166236437695939355252697103801778677462085188924098182725088076503022685270760387219787300737538930978100645525578032205449174673556667517367894515395044506363952919291724514494639967260603654321435026048162210374865422028485743476872381190036845593067721505484899641669193471741435203077087818965534970827237008861720546333776398691518094206301299430723362960542655592512483605052144449911147446383972761571180832477426059987410922498622599233890416001827659244246018252661317668176588876191524476644458278180175907595564089578464053541289889658353085449595345638114956277894377440265809187328746620700929660403607063956264728957200026182242546508904331365657393956953665405467709075021873746717301068844742812640804898358450341147006070992231114309620413797728305363944857231248633777215681178048714555960583285769423269577347092318452597959376442984898597806086880665642171452358839585066290931829822758230731077830945167265530809939378117473625279556317267462647249640436890625269088579237115076783934027795187388832606550708659435481536443442236758890740290467476423736762596428858930168539918890341426049891374123602486910741965206888619217749898476459891203923419562022513871112849590210261873642501502900252092855836815672262020860038323118100356786638630880435236412040943537555010407001968832788551740072702579610201398332444667655843894415660856081122556945790699471646832

Or is it just a really heavy program that I just have to wait?

Let’s look at one example `n == 5` that will call `f(4)` and `f(3)`. those in turn will call `f(3)`, `f(2)`, `f(2)` again and `f(1)`. As you can see there is a lot of superfluous evaluations, and this snowballs when you go to larger `n`.

So, just keep track of what you’ve already computed and things will speed up dramatically:

```def f(n):
res = 0;
if n == 0:
return 0
elif n == 1:
return 1
else:
res=(4*(f(n-1)))+f(n-2)
return res

def f_all(n):
res = (n+1)*[0]
res[1] = 1
for i in range(2, n+1):
res[i] = 4*res[i-1] + res[i-2]
return res

print f(10) == f_all(10)[-1]
print f_all(2424)[-1]
```

Update: Couldn’t resist adding the high-tech solution. It evaluates the closed form solution using the matrix representation of what maths snobs would call the ring Z[sqrt(5)]. This is necessary because floats are just not accurate enough if n is large.

```def f_high_tech(n):
import numpy as np
powpow2_p = np.array([[2, 1], [5, 2]], dtype=object)
power_p_n = np.identity(2, dtype=object)
while n > 0:
if n&1:
power_p_n = np.dot(power_p_n, powpow2_p)
powpow2_p = np.dot(powpow2_p, powpow2_p)
n >>= 1
return power_p_n[0, 1]

print f(10) == f_all(10)[-1]
print f_all(2424)[-1] == f_high_tech(2424)
print f_high_tech(1<<20).bit_length()
```