Any Way To Make Recursive Functions Faster?

After some research about recursive functions i am facing contradiction: On one side solving problems in recursive way is elegant while on the other side in practice performance se

Solution 1:

Ignoring the fact that fibonacci() is a textbook case for memoization (which would make it much faster), "deep and cheap" recursion simply is not a thing in plain Python.

In many languages there is tail-call elimination. Python doesn't have this. In many languages, pushing an additional stack frame is very cheap. Not so in Python.

It's not so easy to find real-world code where this is a problem, which may go some way toward explaining why the Python folks have kept it simple and always create bona fide stack frames with full debugging ability. There's just not a lot of demand for cheap and deep recursion in most Python applications.

Solution 2:

The problem with recursive functions is that you call the same method with the same parameter a certain number of times. For example, in fibrecursive(7), fibrecursive(2) is called 4 times. Each time you redo the same thing.

You can improve performance using dynamic programming. In short, you store your result in an array and when you call fibrecursive(2) you check in your array if it already exists.

Here is the pseudo code from the article:

function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]