Any way to make recursive functions faster?

Question

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.

The recursive fib function is likely noticeably worse since each "iteration" spawns 2 more calls to itself. That would make it O(n*2) vs O(n) if I'm not mistaken. Have you found other recursive functions to be slower than their iterative version? — Carcigenicate, May 26 '17 at 12:02
Recursie fibonacci calculation is a perfect fit for memoization. https://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python — Tomalak, May 26 '17 at 12:05
https://docs.python.org/3/library/functools.html#functools.lru_cache might help for meomization. and: is your question about general recursion or just fibonacci? — hiro protagonist, May 26 '17 at 12:05
If was thinking about that option but both calls shoud be stored in the stack anyway and O(n) = O(n*2) from what i remember since both are petty much linear. I ofetn noticed slowness using recursion but didnt do side by side compparison since i usualy write either one or the other version of code. — codeprimate123, May 26 '17 at 12:10
@codeprimate123 The naive recursive implementation is O(2^n), not O(n*2). — chepner, May 26 '17 at 12:29
@chepner runtime is exponential bcs of the double call specifically in this case and is not inherent to recursion in general right? — codeprimate123, May 26 '17 at 12:48
@codeprimate123 Right. It's not even the double call specifically that makes it exponential, but the fact that the double calls result in the same calls being made repeatedly. The call tree forms a (mostly) complete binary tree, whose size is exponential in the height of the tree. Merge sort is an example of a recursive algorithm that makes two recursive calls, but is O(n lg n). — chepner, May 26 '17 at 12:52

score 2 · Accepted Answer · answered May 26 '17 at 12:05

2

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.

answered May 26 '17 at 12:05

John Zwinck

239,568
38
324
436

Could memoization alse be called hashing? it seems to me very similart concept. So basically if recursion is only way i found to solve a problem i should use memoization if possible or write in some oother language? – codeprimate123 May 26 '17 at 12:20
Memoization is just associating the arguments of a function with the result of evaluating the function on the arguments. Hashing is one way to implement it. – chepner May 26 '17 at 12:38

score 1 · Answer 2 · edited May 26 '17 at 12:11

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]

Any way to make recursive functions faster?

2 Answers2

Linked

Related