11.10 Рекурсия и работа с кучей (повторение)

Указатели

Си: указатель — это адрес (номер ячейки памяти), начиная с которого лежит содержимое переменной
⇒ указатель — это такой unsigned long int (не обязательно именно long — зависит от архитектуры!)
- На x86_64 занимает 8 байт
Указатели типизированы, чтобы работала адресная арифметика:
- int *p ⇒ (unsigned long int) (p+1) == (unsigned long int) p + 4
- char *p ⇒ (unsigned long int) (p+1) == (unsigned long int) p + 1
- int **p ⇒ (unsigned long int) (p+1) == (unsigned long int) p + … сколько?
void * — это вообще любой указатель, его надо явно кастить

Передача указателя в функцию

…нужна для того, чтобы у функции был побочный эффект (изменение каких-то нелокальных переменных)

Самый частый случай (в нашем Д/З) передачи указателя в функцию? передача массива
Зачем передавать указатель на обычную переменную? чтобы её изменить
Зачем передавать указатель на указатель?
swap(char **a, char **b)
strmax(char *a, char *b, char **strmax) — вызывает strcmp() и в зависимости от результата записывает указатель в strmax

Передача функции в виде указателя

Пример — функция triple(fun, a, b, c), которая возвращает fun(fun(a, b), c) + add(a, b)
Создать массив указателей на функцию, положить туда add и mul (написать mul; для фана можно ещё бинарных функций понаделать копипастой), во вложенном цикле вывести все варианты triple для конкретных a, b, c
- тип (*имя_массива[размер]) (типы_параметров) = {add, mul, NULL};

Работа с кучей

Бывает по-разному, но обычно у запущенной программы в ОС:

↓ стек
недоступная память
↑ куча (вы находитесь здесь)
статическая память

Почему так? Так пошла эволюцияПотому что!!! (+потому что виртуальная память, а так удобнее)

Вид памяти	Тип переменных	Где размещается	Время жизни	Объём	Можно ли из функции возвращать указатель
Статическая	Глобальные, статические	В коде программы (секция `data`)	Всё время работы программы	Ограничен здравым смыслом (если проинициализировать, лежит прямо в файле с программой)	Да
Локальная	Локальные	В секции `stack`, доступной после запуска	От входа в функцию до выхода из неё	Ограничен размером стека (зависит от архитектуры; может быть небольшим)	Нет
Динамическая	таких нет, только указатели	В куче, доступной после запуска	От момента явного выделения памяти до момента явного освобождения	Актуально неограничен	Да, но надо быть уверенным, что никто из получивших указатель не будет им пользоваться после того, как память освободили

⇒ Динамическая память нужна, если вам требуется заказать неизвестно сколько памяти для работы, и пользоваться ею примерно всегда после заказа

Malloc, Calloc и free

Отличаются формулой для размера — и тем, что calloc() зануляет выделяемую память
Возвращают void * — не нужно кастить к типу переменной

Realloc

realloc: «увеличение» выделенного буфера
- ```
   1 int main(void) {
   2         int n=9;
   3         char *buf=malloc(n);
   4         for (int i=1; i<1024; i+=43) {
   5                 buf = realloc(buf, n*i);
   6                 printf("%p: %d\n", buf, n*i);
   7         }
   8         free(buf);
   9         return 0;
  10 }
```
- это не увеличение!
- (иногда!) выделяется новый (больший) буфер, в него копируется старый, старый уходит в free(), возвращается новый
  - Почему «иногда»? Так пошла эволюцияПредположительно, потому что ОС в действительности выделила больший буфер
Написать функцию char *getlines(int n), которая вводит n строк в одну (\n удалять не надо), возвращая указатель на эту многострочную строку. Проверить, всё ли в порядке с -fsanitize=address
- Подсказка: fgets() → realloc() → strcat() и так по кругу

Getline и Getdelim

Работа getline

Ввод строки произвольного размера (для этого надо инициализировать приёмник NULL-ом)

(требуется free()):

   1         char *s=NULL;
   2         size_t buflen;
   3         ssize_t len;
   4         while ((len=getline(&s, &buflen, stdin)) > 0)
   5                 printf("%ld, %lu, %s", len, buflen, s);
   6         free(s);
   7         return 0;

⇒ Если s != NULL, а вводимая строка больше bufsize, произойдёт realloc()

Переписать getlines() с использованием getline(). Проверить, всё ли в порядке с -fsanitize=address

Рекурсия

С точки зрения Си рекурсия — это «всего лишь» когда функция {в конце концов} вызывает саму себя.

Рекурсивный вызов — вызов, который приводит в входу в ту же самую функцию
Контекст вызова — данные, с которыми работает рекурсивная функция
Цепочка вызов (или стек вызовов) — когда функция вызвала саму себя, а та снова вызвала саму себя, и так несколько раз
- Контексты в цепочке вызовов все строго разные почему?
Основание рекурсии: условие, при котором вызов не происходит

Уместность рекурсии

Объём входных данных ⩽ log вложенности рекурсивных вызовов

Написать функцию, которая на вход получает счётчик, заводит инициализированный локальный массив размером 1 килобайт, выводит счётчик и бесконечно вызывает себя, увеличивая счётчик на 1

ЧаВо

Q: Бывают ли задачи, которые решаются только рекурсивно?
- A: Нет. Любая рекурсия моделируется циклом + хранилищем контекстов
Q: В каком случае рекурсивное решение (на Си или Python) эффективнее / быстрее итеративного?
- A: Ни в каком. Но в некоторых других ЯП (особенно функциональных) это утверждение неверно
Q: Зачем тогда решать задачу рекурсивно?
- A: Just for fun — это тренирует иной способ думать!
- A: Для некоторых задач рекурсивное решение в несколько раз короче и понятнее итеративного.
Q: Какие задачи проще решать рекурсивно?
- A: 🤔…

Q: Какие задачи проще решать рекурсивно?

Заданные рекуррентными соотношениями (например, числа Фибоначчи, факториал, вообще всякое
- Следите за уместностью рекурсии (объём входных данных ⩽ log вложенности рекурсивных вызовов)
- Следите за паразитными вычислениями (например, рекурсивные числа Фибоначчи — это ужасно)
  - Написать рекурсивную функцию для n-го числа Фибоначчи, вычислить 50-е (40-е? 30-е?)
Задачу можно свести к рекуррентному соотношению
В решении можно выделить одну или несколько подзадач, которые решаются тем же алгоритмом, но работают с меньшим числом входных данных
- Объём из N обрабатываемых данных при рекурсивном вызове сокращается не на константное число элементов, а в k раз (путь даже k близко к 1), или (как в случае задачи с ферзями) — на число, кратное $$\sqrt N$$
- У рекурсивной функции оказывается непустой значимый контекст (переменные, которые меняются от вызова к вызову, по после возврата — восстанавливают значение)
  - Особенно когда рекурсивных вызовов более одного.
- Пример: задача о ферзях. На иллюстрации — третий шаг классического алгоритма
  - Сведение к меньшей подзадаче (в упрощённом виде): поставить ферзя на доску N×N — это цикл по всем возможным позициям ферзя в N-й вертикали + проверка, можно ли поставить ферзя на доску N-1×N
  - Зелёным цветом отмечена область, в которой могут произойти рекурсивные вызовы (не находящиеся под боем пола) + розовым — находящиеся подбоем только по диагонали. Даже если забыть про диагонали (посчитать все цветные квадраты), на k-м шаге из рассмотрения исключается более, чем k*2-1 поле.
    - ⇒ в действительности задача N×N сводится к N проверок и задаче N-1×N-1 — и это свидетелсьтво уместной рекурсии

TODO пример задачи, которая сводится к простому рекуррентному соотношению (желательно, с достаточно простым рекурсивным решением)

Если успеем — ещё что-нибудь поразбираем

Д/З (можно делать)

Напоминаю, что в заданиях типа «написать функцию» сдавать надо именно текст функции, к которому будет приписана тестирующая её программа. Функции main() в этих решениях нет: его допишет EJudge. Если это не оговорено отдельно, допускается также необходимые #include, объявление глобальных переменных и второстепенных функций.

EJudge: ManyGetlines 'Много строк'

Написать программу, вводящую неизвестное количество строк getline()-ом. Массив указателей (aka «массив строк») регулярно обновлять с помощью realloc(). Вывести (с помощью strstr()) все строки, которые содержат последнюю. Конец ввода — EOF, переводы строки исключаются из поиска. Не забыть вызвать free() для всех заказанных на куче фрагментов памяти.
Input:
```
    October 2026       November 2026      December 2026
Su     4 11 18 25      1  8 15 22 29         6 13 20 27
Mo     5 12 19 26      2  9 16 23 30         7 14 21 28
Tu     6 13 20 27      3 10 17 24         1  8 15 22 29
We     7 14 21 28      4 11 18 25         2  9 16 23 30
Th  1  8 15 22 29      5 12 19 26         3 10 17 24 31
Fr  2  9 16 23 30      6 13 20 27         4 11 18 25
Sa  3 10 17 24 31      7 14 21 28         5 12 19 26
7 14
```
Output:
```
Mo     5 12 19 26      2  9 16 23 30         7 14 21 28
We     7 14 21 28      4 11 18 25         2  9 16 23 30
Sa  3 10 17 24 31      7 14 21 28         5 12 19 26
```
Вы будете смеяться, но хороший пример рекуррентного соотношения с уместной рекурсивной реализацией… — числа Фибоначчи!
- EJudge: FibPair 'Числа фибоначчи-2'
  Рекурсивный алгоритм вычисления последовательной пары xчисел Фибоначчи
  - $$ F(2k) = F(k)(2F(k+1) - F(k)) $$ (если нужно чётное по номеру число Фибоначчи)
  - $$ F(2k+1) = F(k)^2 + F(k+1)^2 $$ (если нужно нечётное по номеру число)
  Написать рекурсивную функцию fib(int n, int *f, int *f1), которая записывает в f и f1, соответственно, n-е и n+1-е числа Фибоначчи (нумерация начинается с 0: 0, 1, 1, 2, 3, 5, 8, 13, …).
  - Пример тестирующей программы:
    1 #include <stdio.h> 2 int main(void) { 3 int f, f1; 4 int n; 5 while (scanf("%d", &n)>0) { 6 fib(n, &f, &f1); 7 printf("%d: %d\n", n, f); 8 } 9 return 0; 10 }
  Input:
```
0 1 6 7 8 10 30
```
  Output:
```
0: 0
1: 1
6: 8
7: 13
8: 21
10: 55
30: 832040
```
EJudge: SudanFun 'Быстро растущая функция'
Написать какую угодно (добрый совет: рекурсивную) функцию, unsigned long sudan(int n, unsigned long int x, unsigned long y), вычисляющую следующее рекуррентное соотношение
- $$ F_0 (x, y) = x+y $$
- $$ F_{n+1} (x, 0) = x$$, если $$ n⩾0 $$
- $$ F_{n+1} (x, y+1) = F_n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1)$$, если $$ n⩾0 $$
Функция растёт очень быстро, так что в тестах n, x, и y будут достаточно малы, чтобы не вызывать переполнения unsigned long и исчерпания стека вызовов. Тестовая программа может выглядеть так:
- ```
int main(void) {
        int n, x, y;
        while(scanf("%d%d%d", &n, &x, &y)>0)
                printf("%lu\n", sudan(n, x, y));
        return 0;
}
```
Input:
```
0 0 0
1 4 1
1 2 4
2 1 2
1 1 10
2 2 2
```
Output:
```
0
9
58
10228
3060
15569256417
```
EJudge: RevBraces 'Скобки назад'
Рассмотрим правильную скобочную последовательность, в которой любая пара () скобок может содержать внутри себя буквы — например (qwe) или (qwe)()((rty)(uio)). Применим к ней следующий рекурсивный алгоритм:
1. Если строка — это скобочная последовательность, содержащая единственную пару скобок (в начале и конце), просто выведем всю строку со скобками
2. Если строка содержит несколько скобочных последовательностей, применим наш алгоритм к каждой из них в порядке от последней до начальной, не забывая выводить их скобки
Написать итеративный алгоритм решения этой задачи — функцию backwards(char *str), которая выводит скобочную последовательность с буквами, преобразованную в соответствии с правилами. Тестирующая программа может выглядеть так:
- 1 #include <stdio.h> 2 #include <stdlib.h> 3 int main(void) { 4 char *s; 5 size_t n, l; 6 l = getline(&s, &n, stdin); 7 s[l-1] = 0; 8 backwards(s); 9 free(s); 10 return 0; 11 }
Input:
```
(qwe)(()((rty)(uio)))
```
Output:
```
(((uio)(rty))())(qwe)
```

LecturesCMC/AL/Prac/20_MallocRecursion (последним исправлял пользователь FrBrGeorge 2026-11-14 14:02:15)