Задачі: Рекурсія

Практичні задачі на тему рекурсії.

Формат задач

У кожній задачі дано сигнатуру функції. Потрібно написати рекурсивну реалізацію замість .... Всі функції, що працюють з масивами, використовують шаблонний vector<T> з лекції.

---

Базова рекурсія

Задача 1: Степінь числа

Обчисліть \(x^n\) рекурсивно, використовуючи визначення: \(x^0 = 1\), \(x^n = x \cdot x^{n-1}\).

double power(double x, int n) {
    ...
}

Приклад: power(2.0, 10) → 1024.0

Задача 2: Сума цифр

Обчисліть суму цифр натурального числа рекурсивно.

int digit_sum(int n) {
    ...
}

Приклад: digit_sum(1234) → 10

Підказка: остання цифра — n % 10, решта числа — n / 10.

Задача 3: Кількість цифр

Порахуйте кількість цифр у натуральному числі рекурсивно.

int digit_count(int n) {
    ...
}

Приклад: digit_count(1234) → 4, digit_count(7) → 1

Задача 4: Переведення в двійкову систему

Виведіть двійкове представлення натурального числа рекурсивно.

void print_binary(int n) {
    ...
}

Приклад: print_binary(13) виведе 1101

Підказка: спочатку рекурсивний виклик для n / 2, потім виведення n % 2.

---

Рекурсія з масивами

Задача 5: Рекурсивний максимум

Знайдіть максимальний елемент у vector<T> рекурсивно.

template<typename T>
T recursive_max(vector<T>& v, int index) {
    ...
}

Приклад: {3, 7, 2, 9, 4} → 9

Задача 6: Рекурсивний підрахунок

Порахуйте, скільки разів значення зустрічається у векторі.

template<typename T>
int recursive_count(vector<T>& v, T value, int index) {
    ...
}

Приклад: {1, 3, 2, 3, 3}, value=3 → 3

Задача 7: Рекурсивний reverse

Розверніть вектор рекурсивно, обмінюючи елементи з країв.

template<typename T>
void recursive_reverse(vector<T>& v, int left, int right) {
    ...
}

Приклад: {1, 2, 3, 4, 5} → {5, 4, 3, 2, 1}

Задача 8: Перевірка відсортованості

Перевірте рекурсивно, чи вектор відсортований за зростанням.

template<typename T>
bool recursive_is_sorted(vector<T>& v, int index) {
    ...
}

Приклад: {1, 3, 5, 7} → true, {1, 5, 3, 7} → false

---

Класичні рекурсивні задачі

Задача 9: Паліндром

Перевірте рекурсивно, чи є масив символів паліндромом (читається однаково зліва і справа).

bool is_palindrome(vector<char>& v, int left, int right) {
    ...
}

Приклад: {'a', 'b', 'b', 'a'} → true, {'a', 'b', 'c'} → false

Задача 10: Швидке піднесення до степеня

Обчисліть \(x^n\) ефективніше, використовуючи властивість:

• \(x^0 = 1\)
• \(x^n = (x^{n/2})^2\), якщо \(n\) парне
• \(x^n = x \cdot x^{n-1}\), якщо \(n\) непарне

double fast_power(double x, int n) {
    ...
}

Підказка: ця версія працює за \(O(\log n)\) замість \(O(n)\).

Задача 11: НСД (алгоритм Евкліда)

Обчисліть найбільший спільний дільник двох чисел рекурсивно.

Формула: \(\gcd(a, b) = \gcd(b, a \mod b)\), базовий випадок: \(\gcd(a, 0) = a\).

int gcd(int a, int b) {
    ...
}

Приклад: gcd(48, 18) → 6

Задача 12: Ханойські вежі

Класична задача: перемістіть \(n\) дисків зі стрижня A на стрижень C, використовуючи стрижень B як допоміжний. Правила: переміщувати по одному диску, більший не можна класти на менший.

void hanoi(int n, char from, char to, char aux) {
    ...
}

Приклад для n=3: функція виводить послідовність ходів.

---

Мемоізація

Задача 13: Фібоначчі з мемоізацією (вектор)

Реалізуйте Фібоначчі з мемоізацією, використовуючи vector<long long> як кеш замість глобального масиву.

long long fib_memo(int n, vector<long long>& cache) {
    ...
}

Підказка: якщо cache[n] ще не обчислене (наприклад, дорівнює -1), обчисліть і збережіть. Інакше — поверніть з кешу.

Задача 14: Підрахунок шляхів у сітці

Є сітка \(m \times n\). Можна рухатися тільки вправо або вниз. Порахуйте кількість шляхів з лівого верхнього кута в правий нижній.

int count_paths(int m, int n) {
    ...
}

Приклад: count_paths(3, 3) → 6

Підказка: \(paths(m, n) = paths(m-1, n) + paths(m, n-1)\). Без мемоізації буде дуже повільно для великих \(m, n\). Додайте мемоізацію!

Задача 15: Кількість способів піднятися сходами

Є сходи з \(n\) сходинок. За один крок можна піднятися на 1 або 2 сходинки. Скільки різних способів дістатися вершини?

int climb_stairs(int n) {
    ...
}

Приклад: climb_stairs(5) → 8

Підказка: це, по суті, числа Фібоначчі! \(ways(n) = ways(n-1) + ways(n-2)\).

---

Складніші задачі

Задача 16: Генерація всіх підмножин

Виведіть усі підмножини масиву {1, 2, 3}.

void subsets(vector<int>& v, vector<int>& current, int index) {
    ...
}

Вивід: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

Задача 17: Рекурсивне сортування вибором

Реалізуйте selection sort рекурсивно: знайдіть мінімум, поставте на перше місце, рекурсивно відсортуйте решту.

template<typename T>
void recursive_selection_sort(vector<T>& v, int start) {
    ...
}

Задача 18: Flatten вкладених дужок

Дано рядок з вкладеними дужками. Перевірте рекурсивно, чи правильно розставлені дужки.

bool check_brackets(const char* str, int index, int open_count) {
    ...
}

Приклад: "(()())" → true, "(()" → false, "())(" → false

---

Лекція: Рекурсія