What is the reason why recursive algorithm is particularly slow?

Recursive calls themselves need to use the system stack, and it takes time to allocate function memory and stack every time. However, this process does not take much time. It can be said that simple recursion itself is not much slower than non-recursion

But in practice, we will find that the recursive processing of some problems, especially recursive problems, will show extremely low efficiency. This problem occurs because of repeated calculation.

For example, using recursion to solve the nth term of Fibonacci sequence, the general recursion formula is

f(n) = f(n- 1)+f(n-2)

f(2) = 1

f( 1) = 1

Please try to simulate the computer running this recursion, and you will find that one of the terms f(x) is calculated more than once. When you calculate f(5), you will try to calculate f(4) and f(3), but when you calculate f(4), you actually have to calculate f(3), so that f(3) is called twice.

Imagine that this process is exponentially expanding, and the efficiency will drop rapidly with the increase of n.

To solve this problem, we can use the idea of rote learning.

Define the memory array r and change the function body to:

Definition f(n):

If r[n] is defined, just return r[n] as the answer.

Otherwise, f(n) = f(n- 1)+f(n-2).

Before returning the value, write it down in r[n].

The efficiency of the improved recursive function is almost the same as that of the recursive algorithm.