Рекурсивные функции

Практический курс по C/C++: https://stepik.org/course/193691

На прошлом занятии мы увидели, что локальные переменные и значения аргументов функции при ее вызове помещаются в стековый фрейм. Благодаря такой организации данных у нас автоматически появляется довольно интересная возможность вызывать функции из самих себя с разными входными данными. Это называется рекурсией. А функции, которые это выполняют, рекурсивными.

Давайте посмотрим на работу очень простой рекурсивной функции:

#include <stdio.h>
 
void rcs(int x)
{
         printf("Down: x = %d\n", x);
 
         if(x > 1)
                   rcs(x-1);
 
         printf("Up: x = %d\n", x);
}
 
int main(void) 
{
         rcs(4);
 
         return 0;
}

Здесь функция rcs() пока значение параметра x больше единицы вызывает саму себя с аргументом x-1, то есть, на единицу меньше. Что в итоге будет происходить? При первом вызове в стек помещается значение параметра x=4 вместе с адресом возврата. Затем, отрабатывает первая функция printf() и на экране отображается строка:

Down: x = 4

После проверки условия снова вызывается функция rcs(3) с аргументом 3. В стек помещается новое значение параметра x=3 и выполнение начинается с самого начала функции. Снова отрабатывает printf() с выводом на экран следующей строчки:

Down: x = 3

И так далее. Для rcs(2) увидим строку:

Down: x = 2

а для rcs(1) строчку:

Down: x = 1

После этого переходим на проверку условия. Оно оказывается ложным, поэтому попадаем на вторую функцию printf(), которая выводит сообщение:

Up: x = 1

Что происходит дальше? Из стека извлекается адрес возврата на вторую функцию printf(), указатель стека перемещается на предыдущий блок данных, в которых параметр x равен 2. Поэтому функция printf() отрабатывает с этим значением x=2. Видим на экране строку:

Up: x = 2

На этом выполнение функции завершается. Снова берется из стека адрес возврата на вторую функцию printf(), указатель стека перемещается на блок с данными предыдущего вызова, в котором x = 3. Получаем строку:

Up: x = 3

И также с последним вызовом:

Up: x = 4

Условно рекурсивный вызов функции rcs() можно изобразить следующим образом:

Сначала срабатывает rcs(3), затем, она вызывает функцию rcs(2), а та, в свою очередь, функцию rcs(1). Последняя функция не продолжает рекурсию, так как условие становится ложным. Сразу отрабатывает вторая функция printf() и текущий вызов завершает свою работу. Осуществляется переход (возврат) к вызывающей функции rcs(2). Она продолжает свое выполнение со второй функции printf(). Затем, также завершает свою работу и мы переходим к функции rcs(3).

Вот принцип работы рекурсии. При этом, когда движение идет вглубь, то имеем прямой ход рекурсии, а при возврате – обратный ход. Максимальное число вызовов рекурсивной функции называют глубиной рекурсии.

Пример использования рекурсивной функции

Надеюсь, общий принцип работы рекурсивных функций вам понятен. И, возможно, остается один важный вопрос, зачем они нужны и где имеет смысл их применять? Давайте для этого рассмотрим реальную практическую задачу. Предположим, у нас есть некоторое игровое поле pole размером 5х5 клеток и в каждой клетке может быть число от 0 до 255. Что это за числа и какую роль они несут сейчас совершенно неважно. Изначально все клетки поля закрыты от игрока. Эту информацию мы будем хранить во втором массиве ppole также размером 5х5. И будем полагать, если клетка ppole имеет значение 0, значит, она закрыта, а иначе открыта. Когда игрок открывает какую-либо клетку со значением 0 на игровом поле pole, то должны автоматически открываться все соседние клетки с нулевыми значениями, стоящие по горизонтали и вертикали. Открытые клетки мы будем помечать значением 1 в массиве ppole. Соответственно, при открытии центральной клетки должны получать следующую картину:

Эту задачу достаточно просто можно реализовать с помощью рекурсивной функции, например, так:

#include <stdio.h>
 
#define N    5
 
void show_pole(const char (*p)[N])
{
         for(int i = 0; i < N; ++i) {
                   for(int j = 0; j < N; ++j)
                            printf("%c ", (p[i][j] == 0) ? '#' : '0');
                   putchar('\n');
         }
}
 
void open_zeros(const char (*p)[N], char (*pp)[N], int i, int j)
{
         if(p[i][j] != 0 || pp[i][j] == 1)
                   return;
 
         pp[i][j] = 1; // открываем клетку
 
         if(i-1 >= 0 && p[i-1][j] == 0) open_zeros(p, pp, i-1, j);
         if(i+1 < N && p[i+1][j] == 0) open_zeros(p, pp, i+1, j);
         if(j-1 >= 0 && p[i][j-1] == 0) open_zeros(p, pp, i, j-1);
         if(j+1 < N && p[i][j+1] == 0) open_zeros(p, pp, i, j+1);
}
 
int main(void) 
{
         char pole[N][N] = {
                            {1, 1, 1, 1, 1},
                            {1, 1, 0, 1, 1},
                            {0, 0, 0, 0, 1},
                            {1, 1, 0, 0, 0},
                            {1, 1, 0, 1, 1},
         };
 
         char ppole[N][N] = {0};
 
         show_pole(ppole);
         open_zeros(pole, ppole, 2, 2);
         
         puts("--------------------");
         show_pole(ppole);
 
         return 0;
}

Здесь функция show_pole() отображает клетки игрового поля. А рекурсивная функция open_zeros() открывает все соседние клетки с нулевыми значениями. Работает она очень просто. Вначале мы передаем ей оба массива и индексы начальной открываемой клетки. Если текущая клетка игрового поля содержит 0, то она открывается и запускается рекурсия во все соседние клетки:

Если в соседних клетках также будет число 0, то она откроется, и рекурсия от нее продолжится дальше. И так, пока вся группа связанных нулевых клеток не будет открыта.

После запуска программы увидим следующий результат:

# # # # #
# # 0 # #
0 0 0 0 #
# # 0 0 0
# # 0 # #

Как видите, все нужные клетки были открыты.

Вообще рекурсивные функции очень удобны, когда нам нужно перебрать некие иерархические данные, которые имеют сложную структуру, и обычными циклами их проходить было бы затруднительно. В частности, рекурсия используется для переборов вершин бинарных деревьев – довольно распространенной структуры данных следующего вида:

Или для перебора каталогов и файлов:

И так далее. Везде, где присутствует иерархичность можно подумать об использовании рекурсивных функций. Но нужно всегда помнить и об их недостатках. Они следующие:

  • рекурсивные вызовы работаю медленнее, чем итерации операторов циклов, поэтому, если задачу относительно просто можно реализовать через циклы, то именно их и следует применять;
  • рекурсия не может идти до бесконечности; программа аварийно завершится, когда фреймовый стек будет полностью заполнен, поэтому если в задаче сложно оценить максимальную глубину рекурсии, то от использования рекурсивных функций лучше отказаться.

Практический курс по C/C++: https://stepik.org/course/193691

Видео по теме