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

Question

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) {
    System.out.println("Answer "+f(2424));
}

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?

Answer 1

A more elegant solution can be implemented using the decorator @lru_cache.

This avoids the hassle of keeping track an storing computed values under a for loop.

Compare these two implementations.

• Without using decorator

In my machine, takes ~1 minute to execute fibonacci_recursive(40)

def fibonacci_recursive(n):
    # Base case
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # Recursive case
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

• Using decorator.

BUT now, takes ~7 millisecs to execute fibonacci_recursive(40)

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_recursive(n):
    # Base case
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # Recursive case
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

The decorator caches the results, avoiding explicit recalculation by checking for the value before trying to calculate it. I found this solution here. Brilliant article!

Answer 2

Lets check by the exact value of that recurrence relation

 F(n)=4F(n-1)+F(n-2) = 1/10*(2+sqrt(5))^n*sqrt(5)-1/10*(2-sqrt(5))^n*sqrt(5) 

F(10) = 416020.0

Well this is very hardcore recurrence, and running time is huge. Take a look on this figure:

it really takes too long to calculate F(2424)

Answer 3

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

Answer 4

There is nothing more you can do really with a high level presentation language. If you really want the best optimization possible, you will need to go assembly. But once you reach that level, you will realize that not much will change. Why? Look at the code. There is not much to optimize. If you go C, you might find great compilers that will give you a good executable, but still for the reason stated below, it wouldn't matter.

Your fibonacci problem

Your current problem has a solution. This solution depends on the input and how you resolve it. Right now looking at your algorithm, you are dealing with an exponential time complexity for resolving the problem: O(2^n). This means that small inputs will give you a good result fast, but 2424 will take a lot of time.

Example

Say that the unit of time is second and you input 2. 2 power 2 would give you the solution in 4 seconds.

Enter 2424. This will take you now 4.97e+729 seconds. This supposes you are using the same hardware in both calculation. Be aware I didn't consider your "times 4" for the left side recursive call.

A solution?

To answer your question now. It won't matter the language you switch too. The time it takes to resolve this is so high using this algorithm that changing language on the same hardware will not matter. Even if you go with a compiled language.

Even parallelizing this algorithm wouldn't be possible because each f(n) result depends on 4*f(n-1) and f(n-2). You would have to rewrite this in a way that make it possible, then get a lot of cores or GPU processing power to handle this. But at this point, I digress.

Start it and go take a walk :)

Answer 5

You can use the matrix exponentiation method for O(logn)

Here's a link that explains it and how to implement it

http://www.geeksforgeeks.org/matrix-exponentiation/