Why recursive function consumes more of processing time than loops?

[bowlofred]

I assume your loop is not written identically.

Recursion means a function call. A function call will take more time and memory than just executing a loop. But the difference isn't huge.

But your program is written in a way where you're redoing your work over and over and over. I'm assuming your loop was not written that way. The slowness is due to the algorithm, not inherently the recursion.

If you add a memoization cache to it, it will complete quickly.

from functools import lru_cache

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

print(fibonacci(40))