10.20 Рекурсия

Форма для сдачи

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

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

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

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

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

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

• Последовательность Фибоначчи

  • рекуррентная формула: $$ F_n = F_{n-1} + F_{n-2}; F_0 = 0, F_1 = 1 $$

  • начальные элементы: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

• Написать функцию fiborec(n), рассчитывающую n-й элемент последовательности Фибоначчи с применением рекурсии

• Написать функцию fiboloop(n), рассчитывающую n-й элемент последовательности Фибоначчи с применением цикла (БЕЗ рекурсии)

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

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

  • рекуррентная формула: a^m = a^m/2 * a^m/2

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

  • если m != 2ⁿ, то на каком-то уровне рекурсии образуется нечетная степень

  • лечим: a^2k+1 = a * a^k * a^k

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

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

• Напишем функцию 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()

Д/З

1. EJudge: MoreLast 'Больше, чем последний'

   Написать неуместно рекурсивную функцию, которая возвращает количество чисел, превосходящих последнее введённое число. Написать программу, которая вызывает эту функцию.

   • Массивы использовать нельзя — каждый рекурсивный вызов хранит и сравнивает введённое число

   • Вводом занимается сама неуместно рекурсивную функцию, main() ничего не вводит

   • Можно пользоваться глобальными переменными
   Input:

   15
   8
   43
   29
   1
   50
   36
   22

   Output:

   4

2. EJudge: AllPermutations 'Перестановки'

   Ввести натуральное N, вывести все перестановки чисел 0…N-1 (порядок не важен)

   Input:

   4

   Output:

   0 1 2 3
   0 1 3 2
   0 2 1 3
   0 2 3 1
   0 3 2 1
   0 3 1 2
   1 0 2 3
   1 0 3 2
   1 2 0 3
   1 2 3 0
   1 3 2 0
   1 3 0 2
   2 1 0 3
   2 1 3 0
   2 0 1 3
   2 0 3 1
   2 3 0 1
   2 3 1 0
   3 1 2 0
   3 1 0 2
   3 2 1 0
   3 2 0 1
   3 0 2 1
   3 0 1 2

3. EJudge: UberPalindrome 'Уберпалиндром'

   Уберпалиндромным называется массив, если он сам палиндромом длины ⩾ 3 (в нём n ⩾ 3 элементов, и array[i] == array[n-1-i] ∀ i), или если его можно разбить на несколько уберпалиндромных массивов. Ввести N, затем целочисленный массив на N элементов. Ввести "YES", если массив уберпалиндромен, и "NO" в противном случае.

   Input:

   13 1 2 1 7 6 4 4 6 7 5 6 6 5

   Output:

   YES

4. EJudge: EvalMax 'Вычисление формулы'

   Ввести в строке и вычислить формулу без пробелов (правильность ввода, как всегда, гарантируется и проверять её не надо); <число> — целое (scanf() сам разберётся).

   • <формула> :: = <число> | ("max" | "min") "(" <формула> "," <формула> ")"

   Input:

   max(min(123,234),max(1,min(777,3)))

   Output:

   123