Видео: YouTube
Тем кто ознакомился с предыдущей статьей ничего страшного не грозит. Речь пойдет о рекурсивных функциях. Если коротко, то это функции, вызывающие сами себя. Рекурсия это мощнейший инструмент, позволяющий решить широкий класс задач. Инструмент этот весьма опасный в неумелых руках. Кроме того, что этот инструмент мощный, он требует хорошего абстрактного мышления. Даже всесторонняя помощь отладчика в среде разработки по началу вряд ли сильно поможет. Но если вдумчиво освоить материал, то все становится понятным.
Простейший пример рекурсивной функции.
Чтобы безболезненно окунуться в эту тему предлагается рассмотреть простую программу.
Из функции main вызывается другая функция с одним параметром. Этот параметр определяет с какого числа начнется обратный отсчет. Внутри функции все до предела просто. В консоль или, как удобнее, на экран выводится число, переданное в параметре, Далее происходит вызов той же самой функции с параметром на единицу меньшим. Само собой, следующий вывод на экран будет числом 2, потом 1, 0 и так далее. Вроде ничего сложного. Давайте все же рассмотрим пример до конца.
Рекурсивный и базовый случаи.
Запускаем программу и увидим, как выводится обратный отсчет, уходящий в минус бесконечность. Он и не думает заканчиваться. Что написали, то и получили. Очень скоро произойдет аварийный выход из программы. Название ошибки, приводящей к таким последствиям — переполнение стека. На английском языке stack overflow. Недавно мы рассматривали технические подробности вызова функции и теперь без труда сообразим в чем причина аварийной ситуации.
А причина в том, что каждый новый параметр функции раздувает стек. Рано или поздно в процессоре сработает часть электронной схемы, контролирующей использование памяти и сработает переход на обработку этой ситуации. Чтобы написать корректно рекурсивную функцию, ее тело нужно поделить на две части. Так называемый рекурсивный случай и базовый случай. Рекурсивный случай мы уже написали, это место, где происходит вызов рекурсивной функции. Допишем базовый случай.
Заметили разницу? Чуть выше появился базовый случай. С рекурсивным их разделяет условная конструкция if (…) else... . Если условие истинно, то выполняется базовый случай, если ложно, то рекурсивный. В данном примере достижение базового случая это когда счет дошел до нуля. В базовом случае необходимо прекратить рекурсию. В нашем случае это сделает выход из функции. Давайте теперь подробно и по шагам. Первый вызов функции передал в стек число 3.
В прошлом выпуске мы говорили, что тройка теперь является элементом стекового фрейма своей функции. Также будет уместно сказать, что это также информационное окружение функции, ее область видимости, если угодно, то это также ее контекст.
Базовый случай не сработал, произошел переход на рекурсивный случай, где вывод числа 3 и выполнение вызова функции с параметром на единицу меньше, то есть с числом 2.
Двойка занеслась в стек и сформировала свой стековый фрейм.
Сейчас нужно осознать, что
функция одна и та же.
Отличия в контексте, в том самом окружении. Изменилось информационное окружение. Функция теперь работает с совершенно другим стековым фреймом.
Пока мы все это осознавали, выполнение функции снова дошло до рекурсивного вызова.
Теперь не будет сюрпризом, что в стек отправится единица.
Каково осознавать, что выполнение функции происходит по одним и тем же машинным инструкциям, а указатель стека при этом выписывает в памяти все новые и новые контексты? Это осознание и есть все самое сложное в рекурсивных функциях. При вызове функции с параметром 0 сработает базовый случай.
Это значит произойдет выход из функции. Очистка стека при выходе из функции вернет нас предыдущий контекст, где лежит 1.
Еще один выход приводит нас к контексту 2. Потом в контекст 3. В заключении мы вернемся в стековый фрейм функции main.
Рекурсивное деление массива.
Немало фундаментальных алгоритмов обработки данных целиком основаны на рекурсии. Например, быстрая сортировка данных. Это перестановка по порядку убывания или возрастания. Математики показали, что эта задача выполняется быстро, когда мы поделим ее на части. Сначала работаем с левой половиной, потом с правой, потом в этих половинах также производится деление на половины и так далее. Эта задача как раз для рекурсии. Сейчас мы не будем заниматься сортировкой массива, а только делением пополам до тех пор, пока не дойдем до соседних друг другу пар чисел.
Итак, в стековом фрейме уже лежит массив. Функция произведет рассечения массива пополам. Параметрами являются указатель на массив, индексы элементов начальный и конечный от какого и до какого заниматься рассечениями. В нашем примере от 0 до 7. Вызов функции сопровождается размещением в стеке ее контекста.
Кроме параметров во фрейм еще помещается переменная center, потому как она объявляется локальной в этой функции. Обратим внимание на красную заливку ячеек памяти массива на модели памяти. В контексте начальный и конечный индексы указывают именно так. Базовый случай не сработает, потому что индексы находятся друг от друга на дистанции больше чем один элемент. Переходим к рекурсивному случаю. Тут рассчитывается центр массива, по которому пройдет рассечение.
Если объяснять просто, то это деление на два. Оператор побитового смещения вправо двоичного числа на один бит уменьшит вес каждого разряда. Такое деление будет без остатка. Если самый младший бит был единицей, то он потеряется и ни в какую дробную часть не уйдет. Если нужны подробности, напишите в комментариях. Битовые операции достойны отдельной статьи. Следующее рассечение должно пройти в отрезке массива от начала до центра и потом от центра, плюс один элемент, и до конца. Эта мысль и обозначена в параметрах вызовов функции.
Обе этих функции рекурсивны, вторая начнет выполняться только тогда, когда рекурсия вернется из первой функции обратно. Это значит будем обрабатывать левую половину массива до победного конца. Потом займемся правой. Заходя в функцию с новым контекстом, замечаем, что указывает он на отрезок от 0 до 3 элементов.
Базовый случай не срабатывает. Новый центр теперь будет между 0 и 3, это 1.
Новые вызовы функции будут происходить с диапазонами от нулевого до первого и после возврата из рекурсии от второго до третьего. В новом контексте дистанция между началом и концом в один элемент, а это значит пора на выход из функции. В предыдущем контексте диапазон от 0 до 3.
После вызова из первой рекурсивной функции происходит второй вызов с диапазоном от 2 до 3 элементов.
Тут снова базовый случай. Выходим из функции.
Уровнем выше уже нечего делать. Теперь мы в том контексте, который изначально поделил нам весь массив на две части.
Осталось зайти в рекурсию и обработать правую половину массива. Как только докопались до конца в правой половине массива, происходит серия выходов из контекстов с поднятием указателя стека до самого фрейма функции main.
Это не самый простой вопрос, но с опытом все понимание придет на 100 %. В будущем мы рассмотрим алгоритмы и структуры данных, весомая часть которых потребует понимания рассмотренного здесь материала.
