Задание 16: Рекурсивные алгоритмы

Типичная формулировка: «Алгоритм вычисления значения функции $F(n)$, где $n$ — целое неотрицательное число, задан следующими соотношениями: $F(0)=...$; $F(n)=...$, если $n>0$ и чётно; $F(n)=...$, если $n$ нечётно. Чему равно значение $F(N)$?» или «Сколько существует таких $n$ в диапазоне $[a;b]$, что $F(n)=k$?»

…

• Рекурсия состоит из базового случая (значение функции при конкретном $n$, обычно $n=0$ или $n=1$) и рекуррентного перехода, выражающего $F(n)$ через $F$ от меньшего аргумента.
• Чётность числа определяется остатком от деления на 2: $n \bmod 2 = 0$ — чётное, $n \bmod 2 = 1$ — нечётное.
• Целочисленное деление (обычно обозначается как $n/2$ в условии таких задач) означает $\left\lfloor n/2 \right\rfloor$ — деление с отбрасыванием остатка.
• Глубина рекурсии — количество шагов от $F(n)$ до базового случая. У функций с одним предыдущим значением глубина равна $n$; у функций вида «делим на 2» глубина порядка $\log_2 n$.
• Разложение числа в двоичной системе: любое натуральное число можно представить как сумму степеней двойки, а операция «$n$ чётно — делим на 2, нечётно — вычитаем 1» соответствует последовательному разбору двоичных разрядов.
• Число единичных битов в двоичной записи числа $n$ иногда называют весом Хэмминга или popcount — это стандартная интерпретация ряда рекурсивных функций деления на 2.
• Сумма арифметической прогрессии: $S = \dfrac{(a_1+a_n)\cdot n}{2}$; сумма квадратов первых $n$ натуральных чисел: $\displaystyle\sum_{k=1}^{n} k^2 = \dfrac{n(n+1)(2n+1)}{6}$ — такие формулы помогают проверять результат прикидочно.
• Число сочетаний $C_n^k = \dfrac{n!}{k!(n-k)!}$ применяется, когда нужно посчитать количество чисел с заданным количеством единичных битов в двоичной записи.

1. Определить тип задачи: нужно найти конкретное значение $F(N)$ или посчитать количество чисел $n$ с определённым свойством результата.
2. Выписать базовый случай и все ветки перехода, обратив внимание на условия (строгое/нестрогое неравенство, чётность/нечётность).
3. Если рекурсия опирается на одно предыдущее значение — построить таблицу от базового случая вверх до нужного $n$, вычисляя каждое значение по формуле.
4. Если рекурсия использует деление на 2 или пропуск через два шага — распознать закономерность на малых числах (0, 1, 2, ..., 10) и сформулировать общее правило (например, что функция считает количество единиц в двоичной записи или сумму определённых слагаемых).
5. Аккуратно проводить арифметику на каждом шаге, особенно операции целочисленного деления и возведения в степень — ошибка на одном шаге ломает всю цепочку. …