Найдите значение рекурсивной функции F(10), если F(n) = F(n−1) + F(n−2) + 1

Решение по шагам

1. 1

   Шаг 1. Понимаем, как читать рекурсивное определение

   Определение состоит из двух частей.

   • База рекурсии: $F(1) = 1$ и $F(2) = 1$. Эти значения даны готовыми, вычислять их не нужно.
   • Рекуррентный шаг: при $n > 2$ значение выражается через два предыдущих: $F(n) = F(n-1) + F(n-2) + 1$.

   Считать удобнее не «сверху вниз» (раскрывая $F(10)$ через $F(9)$ и $F(8)$ и утопая в скобках), а снизу вверх: от базы к нужному номеру, запоминая каждое посчитанное значение. Это ровно то, что в программировании называют переходом от наивной рекурсии к динамическому программированию.

2. 2

   Шаг 2. Считаем первые значения после базы

   Подставляем в формулу по очереди:

   $$F(3) = F(2) + F(1) + 1 = 1 + 1 + 1 = 3;$$ $$F(4) = F(3) + F(2) + 1 = 3 + 1 + 1 = 5;$$ $$F(5) = F(4) + F(3) + 1 = 5 + 3 + 1 = 9.$$

   Главное — на каждом шаге брать два соседних предыдущих значения и не забывать про единицу. Единица прибавляется ровно один раз за шаг, независимо от номера $n$.

   Видно, что значения растут примерно вдвое за шаг, поэтому до $F(10)$ ещё пять строк таблицы.