Рекурсия
02.02.2023
Рекурсия в математике — определение объекта через такой же объект (или объекты), но с другими параметрами.
Например, последовательность Фибоначчи — это последовательность натуральных чисел, в котором каждое следующее число равно сумме двух предыдущих.
Обозначим n-е число Фибоначчи символами Fn
Тогда из приведенного определения получается, что Fn =Fn-1 + Fn-2
Налицо рекурсия: число Фибоначчи определено через два других числа Фибоначчи с меньшими номерами. Эти числа можно вычислить.
Простые рассуждения показывают, что одной формулы недостаточно. Вычислим третье число Фибоначчи, F3. По общей формуле оно равно F3=F2+F1. Но мы не знаем ни F1, ни F2! Их можно найти по той же общей формуле
F2=F1+F0, F1=F0+F-1,
Но F0 и F-1 тоже неизвестны.
Выход в том, чтобы задать первые два числа последовательности. Например, так F1=1, F2=1.
В этом случае можно по формуле последовательно вычислить все числа Фибоначчи для n>2:
F3=F2+F1=1+1=2
F4=F3+F2=2+1=3
…
Итак, чтобы определить рекурсивный объект, необходимо задать:
- Правило, по которому новый объект строиться из уже известных объектов;
- Базовые объекты – один (или несколько) начальных объектов в последовательности.
Рекурсивная подпрограмма вызывает сама себя напрямую или через через другие подпрограммы.
Рассмотрим пример.
Составим процедуру, которая выводит на экран двоичную запись натурального числа. Поскольку число, которое нужно обработать, будет меняться, это должна быть процедура с параметром:
def printBin(n):
...Вспомним алгоритм перевода числа в двоичную систему: нужно делить число на 2, каждый раз выписывая остаток от деления, пока не получится 0. На языке программирования Python этот алгоритм можно записать так:
end — именованный параметр, равный пустой строке, отключает переход на новую строку в конце работы функции print (иначе все цифры будут выведены в столбик).
while n!=0:
print(n % 2, end="")
n = n//2Если выполнить эту программу, например для числа 6, вручную (или с помощью транслятора Python) получим результат 011, хотя 6 = 1102
. Проблема в том, что первой получимпоследнюю цифру двоичной записи, поэтому остатки выводятся в обратном порядке (не так как нужно!)
Есть разные способы решения этой задачи, которые сводятся к тому, чтобы запоминать остатки от деления (например, в символьной строке) и затем, когда результат будет полностью построен, вывести его на экран. однако, можно применить еще один красивый подход, основанный на следующей идее:
Чтобы вывести двоичную запись числа n, нужно сначала вывести двоичную запись числа n // 2, а затем — его последнюю двоичную цифру, которая равна n //2.
Выходит, что решение задачи для числа n сводится к решению той же самой задачи для меньшего числа, n // 2, и еще одному простому действию — выводу остатка.
Это и есть рекурсия.
Такой алгоритм очень просто программируется:
def printBin (n):
printBin (n //2)
print (n % 2, end="")получилось так, что процедура printBin вызывает сама себя, т.е. она рекурсивная.
Проверим, используя ручную прокрутку, как работает приведенная процедура printBin.
Представим , что процедуре представили число 2.
Сначала она вызывает сама себя для значения 2 // 2 = 1, затем — для значения 1 // 2 = 0, и потом еще бесконечно много раз для нуля.
Такие вызовы никогда не закончатся. Поэтому эту бесконечную процедуру нужно выйти из процедуры (и закончить эти вложенные вызовы), когда значение параметра станет равно нулю:
def printBin(n):
if n == 0: return
printBin (n // 2)
print (n % 2, end="")После этого необходимо убедиться, что процедура остновится при любом заданном натуральном числе. Действительно, при каждом вложенном вызове значение параметра делится на 2. в результате когда — нибудь оно обязательно станет равно нулю, и тогда вложенные вызовы закончатся.
Экономист по первому образованию и учитель информатики по второму. Преподаю в школе информатику, программирование, сайтостроение, экономику.