Цель работы - научиться использовать рекурсию при решении задач
1. Объявить функцию
// Что получает функция? - степень n (целое число)
// Что возвращает? - результат 2ⁿ (целое число)
int power_of_two(int n);
2. Создать базовый случай
if (n == 0) return 1; // 2⁰ = 1
3. Определить рекурсивный случай
return 2 * power_of_two(n - 1); // 2ⁿ = 2 × 2ⁿ⁻¹
4. Нужна ли обработка особых случаев?
Отрицательные степени? (можно добавить проверку или расширить функционал)
Большие n? (переполнение целочисленного типа)
5. Реализуйте программу с вызовом функции и вывода результата
Протестируйте и отладьте программу:
n = 0 → 1 // Базовый случай
n = 1 → 2 // Простой случай
n = 5 → 32 // Нормальный случай
n = 10 → 1024 // Большее значение
6*. Исследуйте последовательность рекурсивных вызовов (стек вызовов и возвратов)
Найдите естественную рекурсию в задачах
Произведение цифр числа
Сумма цифр числа
Реверс числа
Является ли число палиндромом?
Перевод натурального числа из одной системы счисления в другую
Вычислить 1 × 2 + 2 × 3 + 3 × 4 +…+ (n-1) × n.
Найти сумму ряда
Число сочетаний C(n, k)
сумма квадратов от 1² до n²
Сумма арифметической прогрессии
// Дано: a₁ = 1, d = 1 (сумма чисел от 1 до n)
// Рекурсия: S(n) = n + S(n-1)
// Пример: S(5) = 5 + 4 + 3 + 2 + 1 = 15
Человек поднимается по лестнице из N ступенек. За один шаг он может подняться на 1, 2 или 3 ступеньки. Сколько существует различных способов подняться наверх?
Вход: Количество ступенек N (0 ≤ N ≤ 15)
Выход: Количество способов
Контрольный пример:
Вход: 4
Выход: 7
(Возможные комбинации: 1-1-1-1, 1-1-2, 1-2-1, 2-1-1, 2-2, 1-3, 3-1)
Вход: 0
Выход: 1 (уже наверху)
Рекуррентное соотношение:
ways(n) = 0, если n < 0
ways(n) = 1, если n == 0
ways(n) = ways(n-1) + ways(n-2) + ways(n-3), если n > 0
Проверьте, правильно ли расставлены круглые скобки в заданной строке. Скобка считается закрытой правильно, если у каждой открывающей есть соответствующая закрывающая.
Вход: Строка длиной до 100 символов (может содержать другие символы)
Выход: "YES" если скобки расставлены правильно, "NO" если нет
Контрольный пример:
Вход: "(a + b) * (c - d)"
Выход: YES
Вход: "((())"
Выход: NO (не хватает закрывающих)
Вход: ")("
Выход: NO (нарушен порядок)
Вычислите количество различных путей из левого верхнего угла в правый нижний угол решётки размером N×M, двигаясь только вправо или вниз.
Вход: Два натуральных числа N и M (размеры решётки)
Выход: Количество путей
Контрольный пример:
Вход: 2 2
Выход: 6
Вход: 1 5
Выход: 1
Вход: 3 3
Выход: 20
Формула:
paths(n, m) = 1, если n=0 или m=0
paths(n, m) = paths(n-1, m) + paths(n, m-1), иначе