Лекция 20: Рекурсия

#include <stdio.h>

/**
* @brief Рекурсивная функция для решения задачи о Ханойских башнях.
*
* Перемещает n дисков с одного стержня на другой с использованием вспомогательного.
*
* @param n Количество дисков для перемещения.
* @param from_rod Стержень, с которого перемещаем диски.
* @param to_rod Стержень, на который перемещаем диски.
* @param aux_rod Вспомогательный стержень.
*/

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    // Базовый случай: Если остался только один диск, просто перемещаем его
    if (n == 1) {
        printf("Переместить диск 1 со стержня %c на стержень %c\n", from_rod, to_rod);
        return;
    }

    // Шаг рекурсии:
    // 1. Переместить n-1 дисков с from_rod на aux_rod, используя to_rod как вспомогательный
    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);

    // 2. Переместить оставшийся самый большой диск с from_rod на to_rod
    printf("Переместить диск %d со стержня %c на стержень %c\n", n, from_rod, to_rod);

    // 3. Переместить n-1 дисков с aux_rod на to_rod, используя from_rod как вспомогательный
    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
    int n = 4; // Количество дисков для примера
    printf("--- Рекурсивное решение задачи о Ханойских башнях (%d дисков) ---\n", n);
    // Вызываем функцию для перемещения n дисков со стержня 'A' на стержень 'C', используя 'B'
    towerOfHanoi(n, 'A', 'C', 'B');
    printf("\n");
    return 0;
}

#include <stdio.h>

/**
* @brief Рекурсивная функция для вычисления n-го числа Фибоначчи.
*
* Наивная реализация, демонстрирующая прямое следование математическому определению.
* Обратите внимание, что для больших n эта реализация неэффективна из-за повторных вычислений.
*
* @param n Порядковый номер числа Фибоначчи (начиная с 0).
* @return int n-е число Фибоначчи.
*/

int fibonacci(int n) {
    // Базовые случаи: первые два числа в последовательности Фибоначчи
    if (n <= 1) {
        return n; // F(0) = 0, F(1) = 1
    }

    // Рекурсивный шаг: каждое последующее число является суммой двух предыдущих
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int num = 10; // Найдем 10-е число Фибоначчи (индекс 10 в последовательности 0, 1, 1, 2...)
    printf("--- Рекурсивное вычисление чисел Фибоначчи ---\n");
    // Выводим число Фибоначчи для заданного номера
    printf("Число Фибоначчи с индексом %d: %d\n", num, fibonacci(num));
    printf("\n");
    return 0;
}

#include <stdio.h>

/**
* @brief Рекурсивная функция для выполнения двоичного поиска в отсортированном массиве.
*
* Эффективно ищет элемент, многократно деля интервал поиска пополам.
*
* @param arr Отсортированный массив целых чисел.
* @param low Нижняя граница текущего интервала поиска (индекс).
* @param high Верхняя граница текущего интервала поиска (индекс).
* @param target Значение искомого элемента.
* @return int Индекс элемента, если найден, иначе -1.
*/

int recursiveBinarySearch(int arr[], int low, int high, int target) {
    // Базовый случай: интервал поиска пуст (нижняя граница превысила верхнюю), элемент не найден
    if (high < low) {
        return -1;
    }

    // Вычисляем индекс среднего элемента в текущем интервале
    // Использование low + (high - low) / 2 предотвращает возможное переполнение для больших low/high
    int mid = low + (high - low) / 2;

    // Базовый случай: элемент найден в середине
    if (arr[mid] == target) {
        return mid; // Возвращаем индекс найденного элемента
    }

    // Шаг рекурсии: Если элемент меньше среднего, ищем в левой половине
    if (arr[mid] > target) {
        return recursiveBinarySearch(arr, low, mid - 1, target);
    }

    // Шаг рекурсии: Если элемент больше среднего, ищем в правой половине
    return recursiveBinarySearch(arr, mid + 1, high, target);
}

int main() {
    // Отсортированный массив, необходимый для двоичного поиска
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]); // Определяем размер массива
    int target1 = 23; // Элемент, который будем искать (присутствует)
    int target2 = 100; // Элемент, который будем искать (отсутствует)
    int result;

    printf("--- Рекурсивный двоичный поиск ---\n");

    // Пример поиска существующего элемента
    result = recursiveBinarySearch(arr, 0, n - 1, target1);
    if (result != -1) {
        printf("Элемент %d найден по индексу %d.\n", target1, result);
    } else {
        printf("Элемент %d не найден в массиве.\n", target1);
    }

    // Пример поиска отсутствующего элемента
    result = recursiveBinarySearch(arr, 0, n - 1, target2);
    if (result != -1) {
        printf("Элемент %d найден по индексу %d.\n", target2, result);
    } else {
        printf("Элемент %d не найден в массиве.\n", target2);
    }

    printf("\n");

    return 0;
}

#include <stdio.h>

/**
* @brief Рекурсивная функция для печати элементов массива.
*
* Обходит массив рекурсивно и выводит каждый элемент.
*
* @param arr Массив целых чисел.
* @param size Размер массива.
* @param index Текущий индекс элемента для обработки (начинать с 0).
*/

void printArrayRecursive(int arr[], int size, int index)
{
    // Базовый случай: если индекс достиг размера массива, останавливаемся
    if (index == size)
    {
        return; // [cite: 234]
    }

    // Действие: печатаем текущий элемент
    printf("%d ", arr[index]); // [cite: 235]

    // Рекурсивный шаг: вызываем функцию для следующего элемента
    printArrayRecursive(arr, size, index + 1); // [cite: 235]
}

int main()
{
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Массив:\n"); // [cite: 236]
    // Вызываем рекурсивную функцию для печати массива, начиная с индекса 0
    printArrayRecursive(arr, size, 0); // [cite: 236]
    printf("\n");
    return 0;
}