CODEWITHSUNDEEP
pythonrecursion
codeprimate123
codeprimate123

Reputation: 71

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 seems to be horrible and number of recursive calls is limited.

I understand by default Pythons recursive depth is limited to 1000, however even in a simple application i get very bad performmance as early as 40 - 50 calls.

Let me give an example:

def fibonacci(n):
    if n == 1 or n == 0:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

This simple recursive function on my PC takes huge amount of time to solve even for low n. For testing i also wrote another function:

def fib_nonrecursive(n):
    fib_seq = [1, 1]
    for i in range(2, n+1):
        value = fib_seq[i-1] + fib_seq[i-2]
        fib_seq.append(value)        
    return fib_seq[i]

Non recursive way is very fast even on big numbers, so definitivly problem cannot be operations involved or size of numbers. So my question is why the recursive way is so slow and is there any way to make it faster? Is there any way to expand resursive depth?

EDIT Since answers suggested using memoization i looked into it and implemented it on my example:

def mem(f):
    memory = {}
    def inner_function(x):
        if x not in memory:            
            memory[x] = f(x)
            return memory[x]
        else:
            return memory[x]
    return inner_function

@mem
def fibonacci(n):
    if n == 1 or n == 0:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Same mem(f) can be used with other recursive functions f. The @mem part must be included for f to be passed as argument to mem() (see "decorators") It is slightly advanced way to code but i didnt find an easier was to implement memoization for given example. If there is simpler way of implementation pls correct me.

Upvotes: 2

Views: 5713

Answers (2)

Paltoquet
Paltoquet

Reputation: 1234

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]

Upvotes: 1

John Zwinck
John Zwinck

Reputation: 249123

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.

Upvotes: 2

Related Questions