Рекурсия

Лекция 9 Рекурсия Немного потренировавшись писать и вызывать функции, возможно вы задавались вопросом, можно ли вызывать функции из других функций? Ответ — очевидно, да. Ведь это мы и делаем, когда вызываем функции из main. Напоминаю, что main — это тоже функция. Но могут ли функции вызывать сами себя? И снова ответ: да. //функция, вызывающая себя void CallMyself() { CallMyself(); } //основной код int main(void) { CallMyself(); return 0; } Называется это рекурсией. Как видно из кода, это создает просто бесконечный цикл, и через несколько секунд программа крашнется, сообщив, что стэк переполнен (stack overflow). Вообще, программисты в своей жизни нередко видят эту надпись, она необязательно означает, что есть бесконечная рекурсия, но это, пожалуй, самая частая причина. А что если сделать рекурсию не бесконечной? Нужно поставить условия выхода и тогда этот прием станет по истине эффективным. //Рекурсия int CallMyself(int count) { if (count > 10) { return count; } count++; printf("before: %i\n", count); CallMyself(count); printf("after: %i\n", count); } //основной код int main(void) { printf("Result: %i", CallMyself(0)); return 0; } Этот код уже не приводит к вылету программы, но ничего толкового не делает. Однако мы можем понять, что рекурсия не очень простой инструмент. Важно понимать, как он действует. Вывод программы: before: 1 before: 2 before: 3 before: 4 before: 5 before: 6 before: 7 before: 8 before: 9 before: 10 before: 11 after: 11 after: 10 after: 9 after: 8 after: 7 after: 6 after: 5 after: 4 after: 3 after: 2 after: 1 Result: 0 Когда функция вызывает сама себя, в стеке выделяется место для новых локальных переменных и параметров. Код функции работает с данными переменными. Рекурсивный вызов не создает новую копию функции. Новыми являются только аргументы. Когда каждая рекурсивно вызванная функция завершает работу, старые локальные переменные и параметры удаляются из стека и выполнение продолжается с точки, в которой было обращение внутри этой же функции. Рекурсивные функции вкладываются одна в другую как элементы подзорной трубы. И текущий пример хорошо это демонстрирует. Функция каждый раз увеличиваем локальный счетчик и вызывает сама себя. Так как параметром передано увеличенное значение счетчика, то он продолжает увеличиваться, пока не станет больше 10. Обратите внимание, что если удалить printf после вызова CallMySelf(), то в качестве результата мы получим 11, а не 0. Это будет называться хвостовой рекурсией, и она действует подобно циклу. Но самое интересное начинается именно на этом printf после рекурсивного вызова. Мы как бы возвращаемся в старые функции, где значение счетчика было на единицу меньше. Мы проходим от конца, до самого начала, пока значение счетчика не станет равным самому первому. Это 1, так как передавали мы 0. Но он увеличился, это и был самый первый вызов функции. Обратно мы получаем, правда, даже не 1, и даже не первый переданный аргумент. Попробуйте вызвать функцию printf("Result: %i", CallMyself(9)); И результат все равно, останется равным нулю. Почему? На этот вопрос может ответить сам компилятор, если вы компилировали с ключом -Wall, то он выдаст предупреждение 1.c: In function 'CallMyself': 1.c:14:1: warning: control reaches end of non-void function [-Wreturn-type] } ^ которое означает, что управление доходит до места, где отсутствует оператор return, хотя функция не void типа. И это очень серьезное нарушение! Потому что теперь ваш результат зависит только от компилятора! Одни компиляторы выдадут значение 1 или во втором случае 11, как и предполагалось, другие 0, еще одни отрицательное число и т. д. Результат работы данной функции НЕПРЕДСКАЗУЕМ. За такой код коллеги-программисты обычно пообещают оторвать руки, так что следите за предупреждениями компилятора и думайте, что вы пишете. Этот код следовало написать вот так: int CallMyself(int count) { if (count > 10) { return count; } count++; printf("before: %i\n", count); CallMyself(count); printf("after: %i\n", count); return count; } int main(void) { printf("Result: %i", CallMyself(0)); return 0; } Однако он все равно не имеет никакого смысла, так что давайте перейдем к конкретным примерам. Например, вычисление факториала: int fact (int n) { int result = 1; for(int i = 0; i < n; ++i) { result=result*(i+1); } return result; } Довольно стандартный пример, но все же. Через цикл нет ничего проще, но именно на этом примере можно прочувствовать, насколько элегантней выглядит рекурсивный код: int fact(int n) { if(n == 1) return 1; return fact(n-1) * n; } А можно и еще красивее: int fact(int n) { return (n == 1)? 1 : fact(n-1) * n; } Более короткий код и читается приятней. Но давайте разберемся, как же все получается? Условие выхода из рекурсии: если n равно 1. Это понятно. Далее: 1. Факториала от отрицательных чисел не бывает 2. Если будем умножать на 0, то результат будет равен 0. Формула выстраивается в обратном порядке. Сначала программа «уходит в рекурсию», отнимая каждый раз единицу. Получаем 4,3,2,1 (чтобы убедиться поставьте printf в начале функции). Затем программа выходит из рекурсии и продолжает выполнять остальную часть функции (все что после рекурсивного вызова). Я напоминаю, что при возврате старые значения n сохранены. Таким образом мы получаем 1*2*3*4. В итоге последнее значение возвращается в main и мы получаем корректный ответ. Может быть это выглядит сложным, но если сами потренируетесь, то тема станет куда понятнее. Рекурсия, конечно, используется не для красоты. Некоторые алгоритмы слишком сложно записываются при помощи циклов. Выглядит это все настолько громоздко, что даже явные противники рекурсии (а их не мало, в том числе и я) соглашаются, что рекурсия бывает необходима. Однако есть и немало людей считающих, что в рекурсивном стиле думать легче, чем в итеративном (циклами). В чем недостатки рекурсии? Во-первых, это вызов самой функции, который занимает время, и аналогичный хвостовой рекурсии цикл работает быстрее. В современных задачах на современных компьютерах эта разница не играет роли, но когда производительность архиважна, экономят даже на таких пустяках. Во-вторых, есть вероятность переполнения стека. Стек может быть переполнен даже не из-за бесконечной рекурсии, хватит и достаточно глубокой. На современных компьютерах опять же это не очень принципиально, но задачи бывают всякие и второй недостаток более реален. В-третьих, рекурсию можно просто неправильно использовать, в результате время выполнения алгоритма будет не оправдано больше, чем реализация через цикл. Типичный пример: алгоритм вычисления члена из ряда Фибоначчи. В интернете дают простенький алгоритм в одну строку, который работает очень долго на больших числах и есть шанс, что стек переполнится: int fib(int n) { return (n > 2)? fib(n - 1) + fib(n - 2): 1; } Как видите, решение все также элегантно, но здесь раскрываются недостатки рекурсии. Когда вызывается fib(n), то подсчитываются fib(n-1) и fib(n-2). Но когда считается fib(n-1), она снова независимо подсчитает fib(n-2) – то есть, fib(n-2) подсчитывается дважды. Если продолжить рассуждения, будет видно, что fib(n-3) будет подсчитана трижды, и т.д. Слишком много пересечений. В данном случае это проблема не столько рекурсии, сколько ленивости программиста, написавшего такой код. Если не вычислять второй раз значения функций, которые уже были вычислены, то мы существенно сократим время выполнения на больших числах, попробуйте сами написать этот код. И в общем-то все. Рекурсию можно понять лучше, изучая рекурсивные алгоритмы, к сожалению, это не входит в наш курс. Рекурсию можно увидеть и в реальной жизни, например, направьте два зеркала друг на друга. Стек Я обещал, что вернусь к определению стека. Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Вся суть стека сводится к следующему: представьте массив, но вы не можете обращаться к любому элементу только к первому, однако вы можете добавлять элементы в массив на нулевую позицию, сдвигая остальные вправо, или удалять, но только из нулевой позиции, сдвигая элементы влево. В реальной жизни можно представить стопку тарелок, где класть новую тарелку можно только сверху и брать из стопки тоже только верхнюю. Это простейшая структура, которая, однако, показывает очень хорошую скорость при работе с данными. Естественно там, где не требуется постоянно дергать данные из середины или конца. Реализовать собственный стек можно по-разному. Я приведу пример, когда стек не теряет в быстродействии, но ограничен по размеру: #define MaxSize 1000 struct Stack { int elements[MaxSize]; int sp; }; void push(struct Stack *stack, int value) { if (stack->sp+1 >= MaxSize) exit(1); stack->elements[stack->sp++] = value; } int pop(struct Stack *stack) { if (stack->sp-1 < 0) exit(1); return stack->elements[--stack->sp]; } int main () { struct Stack stack = {.sp = 0}; push(&stack, 10); push(&stack, 20); push(&stack, 30); printf("%i\n", pop(&stack)); printf("%i\n", pop(&stack)); printf("%i\n", pop(&stack)); return 0; } Вывод: 30 20 10 Заметьте, что элементы выводятся по принципу LIFO. А также мою маленькую хитрость, чтобы не терять время на сдвиг элементов, я просто добавляю элементы в конец и удаляю также с конца. Давайте перейдем к менее производительным типам данных, но которые по размеру ограничены уже не будут. Списки В чем проблема массивов? Массивы ограничены количеством элементов, даже выделение нового куска памяти не спасает динамические массивы. Операция аллоцирования (malloc, calloc, realloc) очень долгая по времени. Представьте, что вы в цикле добавляете элементы в массив, постоянно выделяя память под все больший кусок. Ваш цикл будет идти секунды, вместо миллисекунд. Выделять память заранее на большой кусок памяти тоже сомнительная идея. Да она в целом хорошая, и она используется в STL (библиотека с++). Но представьте, что вы ограничены по памяти, а на языке Си пишут часто именно в таких условиях. Так что выделять памяти больше, чем нужно, может быть плохой идеей. И мы находим компромисс. Можно выделять память не на весь массив, а на один элемент. При этом ссылаться на него из предыдущего элемента. В результате будет построен целый список элементов. Простейший список — односвязный список. Это структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL (это зарезервированное имя для нулевого указателя, указателя, который указывает на пустоту. По факту это просто 0). В коде это выглядит очень просто: struct node { int value; // поле данных struct node *next; // указатель на следующий элемент }; struct node root; Структура node представляет собой элемент (узел) списка. В ней содержится значение int и указатель на саму себя. Это может показаться странным, как можно объявить переменную типа, который еще не создан? Но мы объявляем и не переменную, а лишь указатель на тип, который все равно равен 4 байтам, так что никакой рекурсии тут нет. Чтобы строить список далее, нам нужно выделить память на элемент и «повесить» его на next предыдущего элемента. Но как добавить элемент в середину? Или как удалить элемент? Это не такие простые операции и существуют специальные алгоритмы, которые легче нарисовать, чем описать. 1. Инициализация списка. Вы должны инициализировать первый элемент списка. Этот элемент называется корнем, будьте осторожны, если вы потеряете указатель на корень списка, вы потеряете весь список. При инициализации важно повесить NULL на указатель next root->next = NULL; 2. Добавление узла в конец. Это просто. Нужно повесить ссылку на новый элемент в next предыдущего элемента. newnode = malloc(sizeof(node)); newnode->next = NULL; root->next = newnode. 3. Добавление узла в середину. Тут сложнее: Нужно перекинуть ссылку на узел в next предыдущего элемента на новый элемент. И в next предыдущего элемента добавить ссылку на новый. newnode = malloc(sizeof(node)); newnode->next = curelem->next; curelem->next = newnode; 4. Удаление из середины Нужно повесить на next предыдущего элемента ссылку, которая висит на next удаляемого. Только затем очистить память. curelem->next = curelem->next->next; 5. Удаление корня списка Нужно просто возвратить из функции ссылку на следующий элемент, очистить память а возвращаемое значение присвоить указателю root. 6. Вывод всех элементов Можно использовать цикл, можно рекурсию, важно, что мы выводим следующие элементы, пока следующий элемент не равен NULL. 7. Обмен 2х элементов в списке Легче поменять их значения, но если принципиально, то вот картинка: Я не привожу код, потому что это ваша задача его написать, если станет очень сложно есть интернет, где все уже десять раз написано. Имейте ввиду, что интернет напичкан не вполне корректным кодом, так что переписывать надо с умом. Потренируйтесь на int и на циклах, только затем переходите к выполнению лабораторной. Иначе погрязнете в ошибках и багах. Лабораторная работа №9 Задание 0. Создать список из студентов, имеющих фамилию и случайные оценки. Вывести на экран, после этого удалить студентов с хотя бы одной двойкой и вывести на экран. Задание 1. Изменить предыдущую лабораторную так, чтобы вместо массивов были односвязные списки. Для работы со списками запрещается пользоваться циклами. Задание 2. Аналогично, но с учетом заданий на предыдущую лабораторную.