10.19 Рекурсия

Backtrace

Вызов функции:

• Создание блока локальных переменных и адреса возврата на стеке
• Переход на адрес начала функции
• Полезная нагрузка
• Освобождение блока локальных переменных
• Возврат к точке вызова

• bt.c:

   1 #include <execinfo.h>
   2 #include <stdio.h>
   3 
   4 void dump() {
   5         void* buffer[128];
   6         int frames = backtrace(buffer, 128);
   7         backtrace_symbols_fd(buffer, frames, 1);
   8 }
   9 
  10 void second() {
  11         dump();
  12 }
  13 
  14 void first() {
  15         second();
  16 }
  17 
  18 int main(void) {
  19         printf("%p %p %p %p\n", main, first, second, dump);
  20         first();
  21         return 0;
  22 }

• gcc -g -O0 -r -rdynamic bt.c

• Это как раз адреса вызывающих друг друга функций (и конкретно куда внутрь функции возвращаться)

Рекурсия в Си

Рекурсия в Си — это просто ситуация, когда функция в конце концов вызывает себя же.

• (не запуская!)

void rec(int a, int b) {
        printf("%d %d\n", a, b);
        if(a)
                rec(0, a);
        else
                b=0;
        printf("%d %d\n", a, b);
}

void main(void) {
        rec(1, 2);
        return 0;
}

• Что выведет эта функция?

• Почему не изменилось значение b?

• Дописать в rec() вывод адресов a и b

Алгоритмическая рекурсия

• это цикл, в котором стек вызовов используется для хранения последовательности данных

• цикл заканчивается, когда достигнуто основание рекурсии

Сколько проходов цикла в примере выше? Что является основанием рекурсии?

• Написать рекурсивную функцию radd(a, b), которая в случае b⩽0 возвращает a (это основание рекурсии), иначе вызывает себя с параметрами ++a, --b

Свободные и связанные переменные

TODO это мутная тема для Си — придётся рассказывать как минимум про локальные функции, а то и про trampoline / замыкание. Закомментировать?

• Написать функцию rinput(int *arr, int n), которая вводит arr[n]…arr[0]; вывести этот массив

  • Каково основание этой рекурсии?

  • Почему элементы вводятся в таком порядке? А как в другом? переставить местами scanf() и rinput()

• …

Принцип уместности рекурсии

• Если вместо рекурсии легко написать цикл — пишите цикл.

• Если в рекурсивной функции, обрабатывающей n элементов, вложенность рекурсивных вызовов пропорциональна n, вы уже написали, цикл, превратите её в цикл.

Критерий уместности: вложенность рекурсивных вызовов при обработке n элементов данных не должна превышать log(n)(строго говоря — O(log(n)), то есть логарифм, умноженный на константу).

• Примеры популярных неуместно рекурсивных алгоритмов

• Примеры популярных уместно рекурсивных алгоритмов

• TODO развернуть. Двоичное возведение в степень a^m для m=2ⁿ

• TODO развернуть. Модификация двоичного возведения в степень для любого натурального m

Указатели на функцию

Как мы уже видели, имена функций — это их адреса, а значит, это указатели. И их можно передавать как параметры! Только тип указать.

• Напишем функцию add(a, b), которая возвращает a + b, и triple(int fun(int a, int b), a, b, c), для которой triple(add, x, y, z) возвращает a + b + c.

• Модифицировать «двоичное возведение в степень» так, чтобы ему передавалась функция

  • Проэкспериментировать с mul() b add()

Д/З

TODO Четыре задачи на рекурсию: тупенькая, две средние, среднесложная

Возможно, тут: https://grep.cs.msu.ru/kufas.ru.patched/programming201.htm или тут http://grep.cs.msu.ru/narhoz-chita.ru/zadachnik/Glava12/index12.htm#z455

Если рекурсия неуместна, сказать об этом