Рекурсия и файлы

8.1 Что такое рекурсия?

Рекурсия (recursion) — это когда функция вызывает саму себя. Услышав об этом впервые, легко удивиться: как функция может вызвать саму себя? Но идея проста: большую задачу мы превращаем в чуть меньшую, но точно такую же задачу.

Представьте два зеркала, обращённых друг к другу. В каждом зеркале — ещё одно зеркало, в нём — ещё одно, и так далее. Рекурсия устроена так же: внутри каждого вызова есть ещё одна, меньшая его копия.

Например, обратный счёт. sanash(3) сначала выводит 3, затем вызывает sanash(2), который выводит 2 и вызывает sanash(1), и так далее. Каждый вызов чуть меньше предыдущего.

8.2 Базовый случай (base case)

Если функция будет вызывать себя бесконечно, она никогда не остановится и программа упадёт. Поэтому в каждой рекурсии обязателен базовый случай (base case) — условие, останавливающее рекурсию. В обратном счёте ниже базовый случай — это n == 0: дойдя до него, функция не вызывает себя, а просто возвращается.

Нажмите кнопку Выполнить и посмотрите, как работает sanash(3):

8.3 Рекурсивный шаг

На рекурсивном шаге задача каждый раз становится меньше и приближается к базовому случаю. Классический пример — факториал. n! — это произведение чисел от 1 до n. Рекурсивное определение очень красивое: n! = n * (n-1)!, а базовый случай — 1! = 1.

Выберите число и посмотрите, как раскрывается факториал:

8.4 Стек вызовов (call stack)

Теперь самое важное: что происходит внутри рекурсии? Каждый вызов функции добавляет в память новый фрейм в стек вызовов (call stack). Это в точности тот же стек (LIFO) с прошлой недели! Вызовы складываются друг на друга, а дойдя до базового случая, по очереди возвращаются, и ответы перемножаются.

С помощью кнопки Следующий шаг понаблюдайте за factorial(4). Зелёный фрейм — это вызов, который возвращается прямо сейчас:

Обратите внимание: вызовы сначала складываются вниз (4, 3, 2, 1), а затем, начиная с базового случая, возвращаются вверх (1, 2, 6, 24). Именно поэтому рекурсия строится на стеке.

8.5 Рекурсия и цикл

Факториал можно было бы написать и циклом. Многие задачи решаются обоими способами. Выбор зависит от наглядности и природы самой задачи:

Коротко: для простого повторения хорош цикл. Но если задача делится на маленькие копии самой себя (обход дерева, папки внутри папок), рекурсия гораздо естественнее и легче читается.

8.6 Пример: Фибоначчи

Последовательность Фибоначчи — знаменитый пример рекурсии. Каждое число равно сумме двух предыдущих: fib(n) = fib(n-1) + fib(n-2). Базовые случаи: fib(0) = 0 и fib(1) = 1. Последовательность: 0, 1, 1, 2, 3, 5, 8, 13, ...

Выберите число и посмотрите результат и саму последовательность:

8.7 Файлы: открытие и закрытие

Теперь вторая тема. До сих пор после завершения программы все данные терялись. Файл хранит данные на диске, поэтому они остаются на месте даже после повторного запуска программы. Чтобы работать с файлом в C, мы сначала его открываем, используем, а затем закрываем.

fopen открывает файл и возвращает на него указатель (FILE *). Второй параметр — режим: он указывает, с какой целью открывается файл:

• "r" чтение (read): для чтения из существующего файла
• "w" запись (write): новая запись, старое содержимое стирается
• "a" добавление (append): дописывание в конец

8.8 Запись в файл

Для записи текста в файл используется fprintf. Он точно такой же, как printf, только первым параметром принимает указатель на файл: fprintf(f, "%s\n", matn). Введите строку ниже и запишите её в файл:

8.9 Чтение из файла

Для чтения из файла fgets читает одну строку, а fscanf читает форматированные данные. Обычно мы читаем файл от начала до конца, строка за строкой, пока файл не закончится. Файл ниже уже готов. Читайте его по одной строке кнопкой Прочитать следующую строку:

Сделайте прогноз

8.10 Глубже advanced

Ещё несколько важных аспектов рекурсии и файлов.

Переполнение стека

Если рекурсия слишком глубокая (или базовый случай задан неверно и она никогда не останавливается), стек вызовов переполняется. Это называется переполнением стека (stack overflow) и приводит к падению программы. Поэтому базовый случай должен быть правильным и всегда достижимым.

Текстовые и двоичные файлы

Файлы бывают двух видов. Текстовые файлы (txt) состоят из символов, которые человек может прочитать. А двоичные файлы (изображения, видео, базы данных) состоят непосредственно из байтов и читаются специальной программой. Оба вида открываются через fopen, отличаются только режим и способ чтения.

Словарь терминов

8.11 Тест знаний

16 вопросов. Чтобы завершить неделю, ответьте правильно как минимум на 11 из них.