Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-21

1 <a>#статьи</a>

2 <ul><li>8 ноя 2022</li>

3 <li>0</li>

4 </ul>Чтобы понять рекурсивные алгоритмы, нужно понять рекурсивные алгоритмы. Или прочитать эту статью.

5 Фото: Bernard Van Berg / Getty Images

6 Журналист, изучает Python. Любит разбираться в мелочах, общаться с людьми и понимать их.

7 Мы уже рассказывали о <a>рекурсии простыми словами</a>и о том, где её можно встретить в реальной жизни. Пришло время объяснить, как и зачем в программировании применяют рекурсивные функции.

8 В давние времена некоторые девушки, далёкие от точных наук, любили погадать, закрываясь ровно в полночь в чёрной-чёрной комнате и ставя свечку между двумя зеркалами. Согласно их поверьям, это открывало портал в потусторонний мир. А математики увидели бы в этом наглядное представление рекурсии.

9 В каждом зеркале отражалась свеча, и отражение этой свечи в другом зеркале, и отражение отражения, и отражение отражения отражения… и так до тех пор, пока девушке не померещится суженый.

10 Предупреждение:не пытайтесь повторить эксперимент! В кадре задействованы только профессиональные каскадёры! Ни одно животное в процессе съёмки не пострадало!

11 Гадание на суженого: наглядная, хотя и несколько инфернальная, демонстрация рекурсивного алгоритмаФото: "ВКонтакте"Выражаясь научным языком, рекурсия - это определение или изображение объекта или процесса внутри самого этого объекта или процесса.

12 Из вышеприведённого определения становится понятно, что рекурсивная функция - это такая функция, которая в процессе выполнения вызывает саму себя. Это свойство бывает полезно при выполнении некоторых задач в программировании.

13 Например, мы хотим написать функцию summa(n), которая считает сумму чисел от 1 до n. Еслиn = 2, то результат будет 1 + 2 = 3. Еслиn = 5, то получится 1 + 2 + 3 + 4 + 5 = 15. Реализовать такой алгоритм можно двумя способами: итерационным и рекурсивным.

14 Итерационный, или пошаговый, способ.Напишем цикл от 1 до n, в котором на каждом следующем шаге будем прибавлять к x номер шага. На языке Python это выглядит так:

15 def summa(n): x = 0 for n in range(1, n+1): x += n return x summa(5) >>> 15Рекурсивный способ.Во втором варианте нужно решить задачу, используя её же саму.

16 summa(5) - то же самое, что 5 + summa(4)

17 summa(4) - то же самое, что 4 + summa(3)

18 summa(3) - то же самое, что 3 + summa(2)

19 summa(2) - то же самое, что 2 + summa(1)

20 summa(1) - это 1

21 Получается, что мы решаем задачу, используя ответ на эту же задачу, но с меньшей величиной входных данных:

22 def summa(n): if n == 1: return 1 return n + summa(n-1) summa(5) >>> 15Схематично работу функции можно обозначить так:

23 Инфографика: Майя Мальгина для Skillbox MediaИз команд summa(n) и возвращает x можно составить лестницу. Это буквально шаги работы рекурсивного алгоритма. Сначала он постепенно уходит вглубь рекурсии - а потом идёт в обратную сторону, возвращаясь к первоначальной функции.

24 На самом деле в большинстве случаев рекурсивную функцию можно заменить циклами: зачастую они работают быстрее и потребляют меньше памяти.

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

26 Вернёмся к нашему примеру с summa(n). Чтобы алгоритм работал, программа должна соответствовать двум требованиям.

27 Помимо рекурсивного случая, когда функция вызывает сама себя ещё раз, должно быть определённое стоп-условие, чтобы этот процесс не продолжался бесконечно и функция могла завершить работу самостоятельно. В программировании это называется базовым случаем.

28 У нас он произойдёт, когдаnстанет равным 1. Мы упростили задачу настолько, что больше нет смысла считать, - и можем просто дать ответ.

29 Чтобы добраться до базового случая, рекурсивной функции приходится вызывать себя определённое количество раз. Такое число самовызовов плюс первоначальный вызов функции называется глубиной рекурсии. В случае summa(5) она равна 5.

30 Чтобы прийти к базовому случаю, мы должны передавать каждой новой функции изменённые данные. Другими словами, нужно изменять аргумент функции.

31 В нашем коде при первом вызовеnбыла равна 5, при втором - 4. И так до тех пор, покаnне стала равна 1. Не сделай мы этого, рекурсия никогда бы не завершилась и бесконечно порождала бы новые функции.

32 В момент, когда функция вызывает сама себя, действие "материнской" функции приостанавливается - и начинается выполнение "дочерней".

33 Но так как рано или поздно программа должна вернуться к "материнской" функции, нужно сохранить данные о её работе. Для этого существует стек вызовов.

34 Разберём это на примере вызова summa(5). Представим, что компьютер хранит данные о функции в виде блока. В нём содержится значение переменнойnи кусок кода, который сейчас выполняется. Пусть он выглядит так:

35 Инфографика: Майя Мальгина для Skillbox MediaВ момент, когда summa(5) вызывает summa(4), создаётся новый блок и кладётся поверх предыдущего:

36 Инфографика: Майя Мальгина для Skillbox MediaПри каждом новом вызове функции на вершине стека оказывается новый блок. Он начинает работать, остальные же в это время ничего не делают и просто хранят данные. Так происходит, пока рекурсия не доходит до базового случая:

37 Инфографика: Майя Мальгина для Skillbox Mediasumma(1) возвращает единицу, завершает работу и покидает стек. Теперь наверху находится summa(2):

38 Инфографика: Майя Мальгина для Skillbox Mediasumma(2) продолжает свою работу с момента, на котором остановилась. Она заканчивает выполнять свою программу и тоже покидает стек. Теперь наверху summa(3). И так происходит с каждой функцией, пока стек не закончится.

39 При прочих равных программы с рекурсивными функциями обычно потребляют больше памяти, чем итерационные. Так происходит потому, что они хранят внутри стека данные обо всех незавершённых функциях.

40 Память и мощность любой техники ограничены, поэтому у стека всегда есть максимально допустимый размер. Например, в Python он равен 1000 вызовов. Если максимум достигнут, а мы пытаемся положить в стек ещё одну функцию, происходит ошибка "Переполнение стека".

41 Кстати, именно в честь этой ошибки назван популярный сайт для вопросов и ответов о программировании<a>Stack Overflow</a>.

42 Рекурсивная функция - это функция, которая вызывает сама себя.

43 Для правильной работы она должна содержать базовый случай и передавать новому уровню рекурсии изменённые данные.

44 Информация обо всех незавершённых функциях хранится в стеке. При этом в каждый момент времени работает только та функция, которая находится наверху стека.

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

46 Python для всех

47 Вы освоите Python на практике и создадите проекты для портфолио - телеграм-бот, веб-парсер и сайт с нуля. А ещё получите готовый план выхода на удалёнку и фриланс. Спикер - руководитель отдела разработки в "Сбере".

48 <a>Пройти бесплатно</a>

49 <a>Бесплатный курс по разработке на Python ➞Пройдите бесплатный курс по Python и создайте с нуля телеграм-бот, веб-парсер и сайт. Спикер - руководитель отдела разработки в "Сбере". Пройти курс</a>