Рекурсия

Вопросы:

·     Рекурсия.

·     Определение рекурсивного алгоритма.

·     Программирование рекурсивных алгоритмов.

Рекурсией называется способ определения множества объектов через это же множество на основе заданных базовых случаев. Многим из вас это определение может показаться сложным, у других может возникнуть вопрос: «Как же множество объектов может определять само себя?». Рассмотрим пример из математики. Числами Фибоначчи называется числовой ряд, в котором первые два числа равны единице, а все последующие являются суммой двух предыдущих. Обратим внимание на то, что это определение состоит из двух частей. Вторая часть определения называется индуктивной, в ней число Фибоначчи определяется через два предыдущих числа, а первая часть определения указывает на те самые базовые случаи, то есть на то, что первые два числа Фибоначчи равны единице.

Использование рекурсии не ограничивается математикой и информатикой. Рассмотрим несколько примеров. Так, англоязычная аббревиатура GNU – название бесплатной операционной системы с отрытым исходным кодом – является рекурсивной. Она расшифровывается как «GNU is not Unix», что в переводе на русский язык означает «GNU не Unix». Существует шутка, которая гласит о том, что для того, чтобы понять рекурсию, нужно сначала понять рекурсию. В сети Интернет популярны изобразительные примеры рекурсии.

Также рекурсию содержит русская матрёшка и даже герб Российской Федерации. В правой лапе двуглавый орёл держит скипетр, увенчанный сверху уменьшенным изображением этого же герба, который, в свою очередь, также содержит скипетр и т. д…

В программировании рекурсия также применяется в виде рекурсивных алгоритмов. Рекурсивными называются вспомогательные алгоритмы, которые напрямую или через другие вспомогательные алгоритмы вызывают сами себя.

Рассмотрим пример. Мы уже знаем, что факториалом натурального числа называется произведение всех натуральных чисел от единицы до него самого. Таким образом мы можем определить, что факториал некоторого натурального числа n! = 1 при n = 1, или же n! = (n – 1)! * n при n > 1.

Напишем рекурсивную функцию вычисления факториала натурального числа. Назовём нашу функцию factorial (n). Она будет иметь один входной параметр – натуральное число n. Тело функции будет содержать ветвление с условием, что n = 1. Если это условие выполняется, то функция вернёт значение 1 и завершит свою работу. В противном случае функция вернёт значение factorial (n – 1) * n. Сохраним написанный модуль и запустим его на выполнение.

def factorial (n):

    if n == 1:

        return 1

    else:

        return factorial (n - 1) * n

Вызовем описанную функцию для числа 4. Действительно 4! = 24. Теперь вызовем функцию для числа 6. Действительно 6! = 720. Написанная нами функция работает правильно.

Подробнее рассмотрим, как именно работает описанная функция на примере её работы при вызове для числа 3. Условие ветвления не будет выполняться, а значит функция снова будет вызвана для числа 2. При этом текущее исполнение функции будет отложено, то есть компьютер запомнит значение локальных параметров функции, а также адрес, по которому нужно будет вернуться после того, как новый вызов функции будет завершён. В новом вызове функции ветвление снова не будет выполняться, а значит функция снова будет вызвана для числа 1, при этом текущий вызов функции будет отложен. В новом вызове функции условие ветвления будет выполняться, а функция завершит свою работу при этом вернув в предыдущий вызов значение 1. Для возвращения в предыдущий вызов будет считан сохранённый адрес возврата и состояния локальных параметров. После этого и второй вызов функции завершит свою работу, вернув значение произведения 1 * 2 в предыдущий вызов. После этого и самый первый вызов функции завершит свою работу, вернув при этом значение 2 * 3, то есть 6.

Рассмотрим ещё одну задачу. Используя рекурсию, найти цифровой корень заданного натурального числа n. Для вычисления цифрового корня числа само число заменяется суммой своих цифр до тех пор, пока числом не станет одна-единственная цифра.

Обозначим через f функцию цифрового корня из натурального числа, а через g – функцию суммы цифр числа. В этой задаче мы можем определить, что f (n) = n, если число состоит из одной единственной цифры, то есть n < 10. В противном случае f (n) = f (g (n)).

Таким образом, нам остаётся решить задачу на вычисление суммы цифр натурального числа. Эту задачу мы решали ранее, но её также можно решить с использованием рекурсии. Сумма цифр натурального числа равна самому числу, если оно состоит из одной цифры. То есть, если число меньше десяти, в противном случае сумма цифр числа равна сумме его правой цифры, выделенной как остаток от деления числа на 10, и суммы цифр оставшегося числа, полученного как число, делённое без остатка на 10.

Начнём написание программы. Сначала опишем функцию вычисления суммы цифр числа. Назовём её SumDigits. У этой функции будет один параметр – натуральное число n, сумму цифр которого необходимо найти. В теле функции будет следовать ветвление, определяющее, состоит ли число из единственной цифры. Так как заданное число является натуральным, условием ветвления будет то, что n < 10. Если это условие выполняется, то функция вернёт значение самого числа и завершит свою работу. В противном случае функция вернёт значение суммы правой цифры числа, то есть n % 10, а также суммы цифр самого числа, делённого без остатка на 10. Описание этой функции завершено.

def SumDigits (n):

    if n < 10:

        return n

    else:

        return n % 10 + SumDigits (n // 10)

Теперь опишем функцию для вычисления цифрового корня из числа. Назовём её DigitalRoot. У неё будет один параметр – натуральное число n, цифровой корень которого необходимо найти. В теле функции запишем ветвление с условием, что в n – одна цифра, то есть то, что n < 10. Если это условие выполняется, функция завершит свою работу, вернув значение n. В противном случае функция вернёт значение цифрового корня из суммы цифр n. Мы завершили описание и этой функции.

def DigitalRoot (n):

    if n < 10:  

        return n

    else:

        return DigitalRoot (SumDigits (n))

Теперь запишем основной модуль. Вначале с помощью инструкции print выведем на экран сообщение о том, что это программа, вычисляющая цифровой корень заданного n. Вторая инструкция print будет выводить на экран запрос на ввод n без перехода на следующую строку. Далее запишем инструкцию для считывания n. По условию задачи это целое число, поэтому при считывании мы будем преобразовывать его значение в целочисленный тип int. После чего с помощью инструкции print выведем на экран сообщение о том, что цифровой корень из n равен значению функции DigitalRoot (n). Описание модуля завершено.

print ('Программа, вычисляющая цифровой корень из заданного N.')

print ('N =', end = ' ')

n = int (input ())

print ('Цифровой корень из числа', n, 'равен', DigitalRoot (n))

Сохраним его и запустим на выполнение. Введём число 125. Сумма цифр этого числа равна 8, а значит и цифровой корень 125 – 8. Снова запустим программу и зададим число 976. Сумма его цифр равна 22. Сумма цифр 22 равна 4. Это и есть цифровой корень из 976. Программа вывела сообщение об этом. Программа работает правильно. Задача решена. Обратим внимание на то, что код описанных рекурсивных функций достаточно короткий и легко читается, то есть он интуитивно понятен.

Как говорилось ранее, когда происходит вызов функции, компьютер сохраняет её текущее состояние, то есть значение её локальных параметров и адрес возврата. Эти данные сохраняются в особую область памяти – стек. Если забыть о программировании, то можно сказать, что стеком называется коробка с дном, но без крышки. Таким образом, любую вещь в эту коробку можно положить только поверх остальных, а извлечь из коробки можно только самую верхнюю вещь. При программировании стек работает аналогично. Он состоит из ячеек, а в процессоре есть специальный регистр, который называется указателем стека. В нём хранится адрес последней занятой ячейки стека.  При первом вызове процедуры в стек записываются значения параметров основной программы, а также адрес возврата. При втором вызове функции происходит запись в стек значений локальных параметров при первом вызове, а также адрес возврата в него. При завершении очередного вызова функции из стека будут извлечены значения её текущих параметров и адрес возврата.

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

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

Мы узнали:

·     Рекурсией называется способ определения множества объектов через это же множество на основе заданных базовых случаев.

·     В программировании рекурсия применяется в виде рекурсивных алгоритмов – вспомогательных алгоритмов, которые напрямую или через другие вспомогательные алгоритмы вызывают сами себя.

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