Why are recursive algorithms slower than their linear counterparts?

Question

Books

I will not give an example code, just remember the calculation of the n-th member of the Fibonacci series: F(n) = F(n-1) + F(n-2). And what is worth reading to know the answer to such questions?

Answer 1

Because this algorithm, being implemented head-on without any caches and accelerators, is not optimal! F(n-2) is calculated twice, F(n-3) three times, F(n-4) five times, and so on. by Fibonacci.
I can’t say what to read (in that edition of Kormen that I have is not enough), I googled “dynamic programming”. Although Cormen will help at first.
PS. In some cases, head-on calculation helps, but with a simple cache, which will reduce the repeatability, if not for all inputs, then at least for the most egregious ones.
ZZY. Programmers don't like recursion for many reasons. 1. It is difficult to set up an emergency stop. 2. The system stack is limited and there is a risk of overflow.

Answer 2

It is not at all a fact that recursive algorithms are slower. I just wrote a test case - enumeration of numbers, all digits of which are different. The recursive form is about 10% faster than the non-recursive form, and it took several times less time to write it.

Answer 3

I see two different issues here.
First, two recursive algorithms can be made. One remembers the result and therefore works linearly, the other does not and works exponentially. I once did a simple illustration on this topic. Algorithms calculate the fourteenth Fibonacci number. On this subject, I would read Cormen in Shen's translation .
The second question is if we have two asymptotically identical algorithms (or so it seems to us). For example, linear loop versus linear recursion with memory. There are no direct answers here. On the one hand, recursion eats up resources on the call stack, on the other hand, memorization can significantly reduce computational costs + there are a set of tricks that allow you to speed up calculations on both sides.