что такое рекурсия в программировании простыми словами
Простыми словами о рекурсии
Dec 19, 2020 · 4 min read
В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.
Рекурсию также можно сравнить с матрёшкой. Первая кукла самая большая, за ней идёт точно такая же кукла, но поменьше. Суть матрёшки состоит в том, что вы можете открывать её и доставать из неё точно такую же куклу, только немного меньше. Такой продолжительный процесс длится до тех пор, пока вы не дойдёте до последней куклы, которая и прервёт цикл. Так выглядит визуальная репрезентация рекурсии.
Не приведёт ли рекурсивная функция к бесконечному циклу?
Вот пример кода того, как можно реализовать функцию обратного отсчёта с использованием рекурсии:
Как прервать рекурсию:
Проще говоря, рекурсия делает то же, что и код ниже:
Плюсы и минусы рекурсивных функций
Чтобы правильно описать плюсы и минусы, давайте взглянем на производительность рекурсии.
Плюсы:
Под этим подразумевается, что рекурсии, в сравнении с циклами, тратят меньше времени до завершения функции. Чем меньше строк кода у нас будет, тем быстрее функция будет обрабатывать вызовы внутри себя. Особенно хорошо это проявляется при буферизации данных, что позволяет оптимизировать и ускорить код.
В программировании мемоизация — это метод сохранения результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения программ. — Википедия
И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.
Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.
Минусы:
Рекурсивные функции занимают значительный объём памяти во время своего выполнения. Это означает, что при каждом вызове функции в стек будет добавляться новый элемент, который будет занимать место до тех пор, пока функция не завершит работу, найдя ответ, либо пока не дойдёт до выполнения базового условия функции.
Что такое «стек»?
Стек — это такая структура данных, которая работает по принципу «Last In, First Out» (последним пришёл — первым ушёл). Таким образом, элемент «проталкивается» в стек и добавляется в его конец, а затем «выталкивается» из стека при удалении.
Стоит ли использовать рекурсии вместо обычных циклов?
Оба этих метода одинаково эффективны для решения задач, однако выбор одного из них зависит от типа проблемы, поставленной перед вами.
Рекурсии эффективны тогда, когда вы работаете с данными, которые слишком сложны, чтобы пройтись по ним с помощью обычных циклов. Стоит также не забывать о ценности памяти и уменьшении времени, идущем вкупе с рекурсивной функцией, в которой накопилось слишком много элементов.
Циклы так же эффективны в плане скорости и оптимизации, они занимают меньше памяти в стеке и их легче понять, потому что в теле цикла содержится больше информации о том, что происходит внутри.
Простыми словами о рекурсии
В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.
Рекурсию также можно сравнить с матрёшкой. Первая кукла самая большая, за ней идёт точно такая же кукла, но поменьше. Суть матрёшки состоит в том, что вы можете открывать её и доставать из неё точно такую же куклу, только немного меньше. Такой продолжительный процесс длится до тех пор, пока вы не дойдёте до последней куклы, которая и прервёт цикл. Так выглядит визуальная репрезентация рекурсии.
Не приведёт ли рекурсивная функция к бесконечному циклу?
Вот пример кода того, как можно реализовать функцию обратного отсчёта с использованием рекурсии:
Как прервать рекурсию:
Проще говоря, рекурсия делает то же, что и код ниже:
Плюсы и минусы рекурсивных функций
Чтобы правильно описать плюсы и минусы, давайте взглянем на производительность рекурсии.
Плюсы:
Под этим подразумевается, что рекурсии, в сравнении с циклами, тратят меньше времени до завершения функции. Чем меньше строк кода у нас будет, тем быстрее функция будет обрабатывать вызовы внутри себя. Особенно хорошо это проявляется при буферизации данных, что позволяет оптимизировать и ускорить код.
В программировании мемоизация — это метод сохранения результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения программ. — Википедия
И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.
Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.
Минусы:
Рекурсивные функции занимают значительный объём памяти во время своего выполнения. Это означает, что при каждом вызове функции в стек будет добавляться новый элемент, который будет занимать место до тех пор, пока функция не завершит работу, найдя ответ, либо пока не дойдёт до выполнения базового условия функции.
Что такое «стек»?
Стек — это такая структура данных, которая работает по принципу «Last In, First Out» (последним пришёл — первым ушёл). Таким образом, элемент «проталкивается» в стек и добавляется в его конец, а затем «выталкивается» из стека при удалении.
Стоит ли использовать рекурсии вместо обычных циклов?
Оба этих метода одинаково эффективны для решения задач, однако выбор одного из них зависит от типа проблемы, поставленной перед вами.
Рекурсии эффективны тогда, когда вы работаете с данными, которые слишком сложны, чтобы пройтись по ним с помощью обычных циклов. Стоит также не забывать о ценности памяти и уменьшении времени, идущем вкупе с рекурсивной функцией, в которой накопилось слишком много элементов.
Циклы так же эффективны в плане скорости и оптимизации, они занимают меньше памяти в стеке и их легче понять, потому что в теле цикла содержится больше информации о том, что происходит внутри.
Рекурсивное программирование
Feb 22, 2019 · 8 min read
При первом знакомстве с концепцией рекурсии, она может показаться странной и отталкивающей. Это кажется почти парадоксальным: как мы можем найти решение проблемы, используя решение той же проблемы? Несмотря на это, в большинстве проектов, рекурсию используют в программировании уже на ранних стадиях производства.
Я думаю, что тем, кто пытается постигнуть концепцию рекурс и и, следует сначала понять, что рекурсия — это больше, чем просто практика в программировании. Это философия решения проблем, которые можно решать частями, не трогая основную часть проблемы, при этом, проблема упрощается или становится меньше. Рекурсия применима не только в программировании, но и в простых повседневных задачах. Например, возьмите меня, пишущего эту статью: допустим, я хочу написать около 1000 слов, и ставлю цель писать 100 слов каждый раз, когда сажусь за работу. Получается, что в первый раз я напишу 100 слов и оставляю 900 слов на потом. В следующий раз я напишу ещё 100 слов, а оставлю 800. Я буду продолжать, пока не останется 0 слов. Каждый раз, я частично решаю проблему, а оставшаяся часть проблемы уменьшается.
Работу над статьей можно представить в виде такого кода:
Также, этот алгоритм можно реализовать итеративно:
Если рассматривать вызов функции write_words(1000) в любой из этих реализаций, вы обнаружите, одинаковое поведение. На самом деле, каждую задачу, которую можно решить с помощью рекурсии, мы также можем решить с помощью итерации (циклы for и while ). Так почему же стоит использовать именно рекурсию?
Почему рекурсия?
Хотите верьте, хотите нет, но с помощью рекурсии некоторые проблемы решить легче, чем с помощью итерации. Иногда рекурсия более эффективна, иногда более читаема, а иногда просто быстрее реализуется. Некоторые структуры данных, такие как деревья ― хорошо подходят для рекурсивных алгоритмов. Существуют языки программирования, в которых вообще нет понятия цикла — это чисто функциональные языки, такие как Haskell, они полностью зависят от рекурсии для итеративного решения задач. Я хочу сказать, что программисту не обязательно понимать рекурсию, но хороший программист, просто обязан в этом разбираться. Более того, понимание рекурсии сделает вас отличным «решателем» проблем, не только в программировании!
Суть рекурсии
В общем, рекурсивный подход подразумевает разделение сложной задачи, на один простой шаг к её решению и оставшуюся часть, которая становится упрощённой версией той же задачи. Затем этот процесс повторяется. Каждый раз вы совершаете один шаг, до тех пор, пока задача упростится до одного простейшего решения (его называют «базовым случаем»). Простейшее решение нашего базового случая с шагами, которые мы предприняли, чтобы добраться до него, образуют решение нашей первоначальной задачи.
Предположим, у нас есть фактические данные определённого типа, назовём их dₒ. Идея рекурсии состоит в том, чтобы предположить, что мы уже решили задачу или вычислили желаемую функцию f для всех форм этого типа данных. Каждая из этих форм проще общей сложности dₒ, которую нам нужно определить. Следовательно, если мы можем найти способ выражения f(dₒ), исходя из одной или нескольких частей f(d), где все эти d проще, чем dₒ, значит мы нашли решение для f(dₒ). Мы повторяем этот процесс, и рассчитываем, что в какой-то момент оставшиеся f(d) станут настолько простыми, что мы сможем легко реализовать фиксированное, окончательное решение для них. В итоге, решением исходной задачи станет поэтапное решение более простых задач.
В приведённом выше примере (про написание статьи), данными является текст, содержащийся в документе, который я должен написать, а степень сложности — это длина документа. Это немного надуманный пример, но если предположить, что я уже решил задачу f(900) (написать 900 слов), то все, что мне нужно сделать, чтобы решить f(1000), ― это написать 100 слов и выполнить решение для 900 слов, f(900).
Давайте рассмотрим пример получше: с числами Фибоначчи, где 1-е число равно 0, второе равно 1, а nᵗʰ число равно сумме двух предыдущих. Предположим, у нас есть функция Фибоначчи, которая сообщает нам nᵗʰ число:
Как будет выглядеть выполнение такой функции? Возьмём для примера fib(4) :
Рекурсивная стратегия
Рекурсивный подход — дело тонкое, и зависит от того, какую проблему вы пытаетесь решить. Тем не менее, есть некоторая общая стратегия, которая поможет вам двигаться в правильном направлении. Эта стратегия состоит из трёх шагов:
Упорядочивание данных
Этот шаг является ключевым для решения проблем рекурсивным способом, и все же его часто упускают из виду или выполняют неявно. Какие бы данные мы ни использовали, будь то числа, строки, списки, бинарные древа или люди, необходимо явно найти целесообразный порядок, который даст нам видение, как упростить задачу. Порядок полностью зависит от конкретной задачи, но для начала стоит подумать об очевидных вариантах. Например: числа можно упорядочить по величине, строки и списки можно упорядочить по длине, бинарные древа по глубине, а люди могут быть упорядочены бесконечным количеством разумных способов: рост, вес или должность в организации. Это упорядочивание должно соответствовать степени сложности задачи, которую мы пытаемся решить.
После того, как мы упорядочили данные, нам нужно подумать об этом, как о чём-то, что мы можем сократить. На самом деле, мы можем записать наш порядок в виде последовательности:
0, 1, 2, …, n для чисел (т.е. для int данных d, степень(d) = d)
Двигаясь справа налево, мы идём от общего («большая часть задачи») случая, к базовым («маленьким частям») случаям. В нашем примере с функцией reverse мы работаем со строкой, и можем взять длину строки за основу, для упорядочивания или определения степени сложности задачи.
Решаем малую часть проблемы
Переходим к общим случаям
Часто бывает так, что нам нужно рассмотреть несколько рекурсивных случаев, так как данные определённого типа, могут принимать разные формы, но это полностью зависит от задачи. Например, если мы хотим сгладить список элементов, некоторые из которых сами могут быть списками, нам нужно будет различать случаи, когда элемент, который мы вытаскиваем из списка, является отдельным элементом или подсписком, что приводит по крайней мере к двум рекурсивным случаям.
Напутствие
Единственный способ улучшить свои навыки в рекурсии — это практика. В интернете можно найти тысяч примеров задач, подходящих для рекурсивного решения — испытайте себя. Однажды, вы неизбежно научитесь рекурсии, но, если у вас возникнут трудности с рекурсивным решением проблемы, попробуйте вместо этого итерацию. Рекурсия поможет вам решать проблемы не только в программировании, но и в повседневной жизни. Если проблема не подходит для рекурсии, что ж, такое бывает; со временем вы научитесь чувствовать, где следует использовать рекурсивный подход, а где итеративный.
Иногда в более сложных рекурсивных задачах, шаги 2 и 3, о которых мы говорили, принимают форму более циклического процесса. Если вы не можете быстро найти общее решение проблемы, попробуйте решить рекурсивные (большие) случаи и базовые (маленькие) случаи, которые сможете найти, а затем посмотрите, как в результате разделились разные части данных. Это должно выявить любые недостающие базовые и рекурсивные случаи или те, которые плохо взаимодействуют друг с другом и нуждаются в переосмыслении.
Наконец, помните, что выявление порядка является самым важным шагом к решению рекурсивной задачи, и ваша цель рассмотреть как правый (рекурсивный), так и левый (базовый) случаи этого порядка, чтобы решить задачу для всех данных определённого типа.
Рекурсия
Рекурсия — это жемчужина теории алгоритмов, и это первое, с чем знакомят школьников (сразу после процедур ввода и вывода данных, элементарных арифметических операций, оператора цикла и условного оператора).
Простота рекурсии обманчива. Метод рекурсии таит в себе много опасностей и сложностей, и в то же время готовит много приятных сюрпризов.
Давно известен такой математический приём, как разбиение задачи на простые шаги, каждый из которых тоже можно разложить на более мелкие шаги и так далее, пока не доберёмся до самых элементарных «шажочков».
Представим, что нужно пройти 1000 шагов. Для решения делаем один шаг, остаётся 999: задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи — шагнуть один раз. Конечно, этот пример слишком прост. Далее мы рассмотрим более сложные примеры, освещающие явление рекурсии как с хорошей так, и с плохой стороны.
Вы, наверное, уже заметили сходство понятий рекурсии и математической индукции. У рекурсии, как и у математической индукции, есть база — аргументы, для которых значения функции определены (элементарные задачи), и шаг рекурсии — способ сведения задачи к более простым.
Содержание
Числа Фибоначчи [ править ]
Современные языки программирования дают возможность программировать рекурсивные определения без особых усилий, но в таких определениях таятся опасности.
Проблемы рекурсии и как их решать [ править ]
Есть способ решить проблему повторных вычислений. Он очевиден — нужно запоминать найденные значения, чтобы не вычислять их каждый раз заново. Конечно, для этого придётся активно использовать память.
Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»:
Такая рекурсия с запоминанием называется динамическим программированием сверху.
Рекурсию с запоминанием для вычисления чисел Фибоначчи мы привели просто для демонстрации идеи. Для чисел Фибоначчи есть простой «человеческий алгоритм», не использующий рекурсивные вызовы и запоминание всех вычисленных значений. Достаточно помнить два последних числа Фибоначчи, чтобы вычислить следующее. Затем предпредыдущее можно «забыть» и перейти к вычислению следующего:
F ( n ) = 1 5 ( ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ) <\displaystyle F(n)=<\frac <1><\sqrt <5>>>\left(\left(<\frac <1+<\sqrt <5>>><2>>\right)^
.
Особенно просто и наглядно функцию вычисления чисел Фибоначчи можно задать на языке Mathematica (см. http://www.wolfram.com):
Простое рекурсивное определение: F(n_) := F(n-1) + F(n-2); F(1) = F(2) = 1;
Рекурсивное определение с запоминанием: F[n_] := (F[n] = F[n-1] + F[n-2]); F[1] = F[2] = 1;
Задача 1 [ править ]
Задача 2 [ править ]
Задача 3 [ править ]
Задача 4 [ править ]
Задача о золотой горе [ править ]
На международной олимпиаде по информатике в 1994 году в первый день среди прочих задач была дана следующая задача.
Формулировка задачи: На рисунке показан пример треугольника из чисел. Написать программу, вычисляющую наибольшую сумму чисел, через которые проходит путь, начинающийся на вершине и заканчивающийся где-то на основании.
В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.
В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.
Пример входных данных:
Эту задачу можно встретить и под названием «Золотая гора» — нужно спуститься с горы и собрать как можно больше золота.
На рисунке обозначены две горки (треугольники): одна с вершиной в числе 3, другая с вершиной в числе 8. Эти горки пересекаются, и их пересечение тоже горка с вершиной в числе 1. Можно заметить, что при вычислении самого лучшего пути по рекурсивному алгоритму горка с вершиной в числе 1 будет использоваться дважды. Для горок с вершинами в нижних строчках повторных вызовов будет ещё больше. Это и есть причина медленности работы алгоритма.
Задача 5 [ править ]
Эта задача показывает, что придумать рекурсивный алгоритм часто намного проще, чем не рекурсивный. Также несложно добавить к рекурсии запоминание вычисленных значений. Но нередко существует более быстрый алгоритм, основанный на динамическом программировании, который использует меньше памяти, нежели рекурсия с запоминанием, и делает в два раза меньше операций обращения к памяти.
Задача «Сделай палиндром» [ править ]
Палиндром — это последовательность символов, которая слева-направо и справа-налево пишется одинаково. Например «АБА» или «АББ ББА». Дана последовательность символов. Какое минимальное количество символов нужно удалить из неё, чтобы получить палиндром?
Длина последовательности не больше 20 символов. Ограничение на время работы программы: 5 секунд.
Эта задача давалась на районной олимпиаде школьников Удмуртской республики в 1998 году. Рассмотрим её решение, основанное на рекурсии.
Алгоритм Евклида [ править ]
Даны два натуральных числа. Найти самое большое натуральное число, которое делит оба без остатка. Такое число называется наибольший общий делитель (НОД) (GCD — Greatest Common Divisor).
Пример: Вход: 18, 600 Выход: 6
Рассмотрим второе свойство. При замене одного из чисел на его разность с первым, наибольший общий делитель остаётся прежним.
3 5 = 1 1 + 1 1 + 1 2 <\displaystyle <\frac <3><5>>=<\frac <1><\displaystyle 1+<\frac <1><\displaystyle 1+<\frac <1><2>>>>>>> , 5 8 = 1 1 + 1 1 + 1 1 + 1 2 <\displaystyle <\frac <5><8>>=<\frac <1><\displaystyle 1+<\displaystyle <\frac <1><\displaystyle 1+<\frac <1><\displaystyle 1+<\frac <1><2>>>>>>>>>> , 8 13 = 1 1 + 1 1 + 1 1 + 1 1 + 1 2 <\displaystyle <\frac <8><13>>=<\frac <1><\displaystyle 1+<\displaystyle <\frac <1><\displaystyle 1+<\frac <1><\displaystyle 1+<\frac <1><\displaystyle 1+<\frac <1><2>>>>>>>>>>>> .
Задача 6 [ править ]
Задача 7 [ править ]
При построении рекурсивной функции важно ответить на следующие вопросы:
Одно из важных достоинств рекурсивных алгоритмов заключается в том, что они просты и наглядны. Но рекурсия не всегда является эффективным (самым быстрым) решением. Рекурсия использует мало памяти, но работать может довольно долго, как в примере с числами Фибоначчи.
Задача 8 [ править ]
Есть несколько алгоритмов Евклида, основанных на различных рекуррентных соотношениях для НОД:
Задачи для самостоятельного решения [ править ]
Существуют и другие задачи, решаемые рекурсией и динамическим программированием. Вот самые известные: обход конём шахматной доски, задача о восьми ферзях, триангуляция, поиск пути в лабиринте, вычисление арифметического выражения и многое другое.
Ниже предлагается несколько простых задач, для знакомства с идеей рекурсии.
Задача 9 [ править ]
Задача 10 [ править ]
Задача 11 [ править ]
Эта строчка содержит рекурсивное определение объекта s : «объект типа s может быть получен из объекта типа s с помощью окружения его открывающейся и закрывающейся круглой скобки, или с помощью приписывания двух объектов типа s друг к другу, либо это просто пустое слово». Вертикальная черта в нотации EBNF означает союз «или». С помощью одинарных кавычек выделяют символы или строки символов, пробелы играют роль разделителей.
Задача 12 [ править ]
Задача 13 [ править ]
Задача коммивояжёра [ править ]
Рекурсия с запоминанием работает не всегда. Рассмотрим пример задачи, для которой есть долго работающий рекурсивный алгоритм, который нельзя существенно ускорить с помощью запоминания вычисленных значений.
Коммивояжёр (франц. commis voyageur), разъездной представитель торговой фирмы, предлагающий покупателям товары по имеющимся у него образцам, каталогам и тому подобное.
Наш коммивояжёр ездит по городам с целью сбыта товаров разного рода. Он всегда начинает и заканчивает свой путь в одном и том же городе. На проживание во всех городах коммерсант тратит одинаковую сумму денег. Поэтому существенна только сумма на проезд из города в город. Есть список городов и стоимость проезда между некоторыми парами городов.
Задача коммивояжёра — побывать во всех городах (не менее одного раза) и при этом потратить как можно меньше денег на проезд и вернуться обратно.
Стоимости проезда между парами городов записаны в следующем формате:
Результат записывается в следующем формате:
Город задаётся названием без пробела. Длина названия города не более 30 символов. Программа должна реагировать на клавишу ESC. Если ESC была нажата, то в течении 10 секунд программа должна записать результат и закончить работу.
Снежинка Коха [ править ]
Снежинка Коха — это фрактальное множество точек на плоскости, которое похоже на снежинку.
Здесь приведена программа на языке PostScript. Этот код интерпрерируется программой GSView, которую можно взять на сайте http://www.ghostscript.com.
Снежинка рисуется рекурсивным образом. Сначала она выглядит как треугольник. Затем на сторонах этого треугольника рисуются треугольные выступы. Получается шеcтиконечная звезда. На сторонах этой звезды снова рисуются треугольные выступы (см. синюю фигуру). Процесс наращивания треугольных выступов можно продолжить до бесконечности и получить в пределе вполне корректно определённое множество точек на плоскости.
Программа «Снежинка Коха»
Заключение [ править ]
Рекурсивный метод решения задач является чуть ли не базовым методом решения алгоритмических задач. Рекурсия, дополненная идеями динамического программирования, жадными алгоритмами и идеей отсечения, превращается в тяжёлую артиллерию программистов. Но не следует забывать, что краткость записи рекурсивных функций не всегда означает высокую скорость их вычисления. И есть ряд задач, в которых рекурсия просто вредна (такова, например, задача вычисления кратчайшего пути в графе).