Зимняя школа в "Эврике"

Теперь мы можем оформить решение этой задачи в виде рекурсивной функции:

Пример на языке Python

# неэффективное решение
def F(n):
    if n < 2:
        return 1
    else:
        return F(n - 1) + F(n - 2)


Пример на языке Pascal

function f(n: longint): longint;
begin
  if n < 2 then
    f := 1
  else
    f := f(n - 1) + f(n - 2);
end;
 

Но при попытке вычислить решение этой функции для уже не очень больших n, например, для n = 40, 
окажется, что эта функция работает крайне медленно. 
И при этом время работы функции с увеличением n растет экспоненциально, то есть такое решение неприемлемо по сложности. 
Причина этого заключается в том, что при вычислении рекурсивной функции подзадачи, для которых вычисляется решение, «перекрываются». 
То есть для того, чтобы вычислить F(n) нам нужно вызвать F(n − 1) и F(n − 2). 
В свою очередь F(n − 1) вызовет F(n − 2) и F(n − 3). То есть функция F(n − 2) будет вызвана два раза — один раз это будет сделано при 
вычислении F(n − 1) и один раз — при вычислении F(n − 2).
Значение F(n − 3) будет вычислено уже три раза, а значение F(n − 4) будет вычисляться уже пять раз. 
При увеличении глубины рекурсии количество перекрывающихся» вызовов функций будет расти экспоненциально.
То есть одна из причин неэффективности рекурсивного решения — одно и то же значение функции вычисляется несколько раз, так как оно 
используется для вычисления нескольких других значений функции.