Что значит рекурсивный метод

Простыми словами о рекурсии

Dec 19, 2020 · 4 min read

В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.

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

Не приведёт ли рекурсивная функция к бесконечному циклу?

Да, такой исход вполне возможен. Однако, как и у функции for или while , рекурсию можно прервать условием break , чтобы функция перестала вызывать саму себя.

Вот пример кода того, как можно реализовать функцию обратного отсчёта с использованием рекурсии:

Как прервать рекурсию:

Допустим, у нас имеется функция CountDown , которая принимает аргумент (n) . Чтобы реализовать обратный отсчёт, нам следует повторить последовательность действий, понижающих значение параметра. Создадим условие вида:

Если (n) больше 1 , то вызвать функцию CountDown и вернуться в начало цикла, затем вычесть единицу и снова проверить, выполняется ли условие (n) > 1 .

По умолчанию нам нужно создать базовое условие функции, возвращающее значение true , чтобы предотвратить попадание в бесконечный цикл. Базовым условием функции здесь будет условие о том, что любое значение больше 1 не вызовет прерывание цикла.

Проще говоря, рекурсия делает то же, что и код ниже:

Плюсы и минусы рекурсивных функций

Чтобы правильно описать плюсы и минусы, давайте взглянем на производительность рекурсии.

Плюсы:

• Рекурсивный код снижает время выполнения функции.

Под этим подразумевается, что рекурсии, в сравнении с циклами, тратят меньше времени до завершения функции. Чем меньше строк кода у нас будет, тем быстрее функция будет обрабатывать вызовы внутри себя. Особенно хорошо это проявляется при буферизации данных, что позволяет оптимизировать и ускорить код.

В программировании мемоизация — это метод сохранения результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения программ. — Википедия

И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.

Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.

Минусы:

• Рекурсивные функции занимают много места.

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

• Рекурсивные функции замедляют программу.

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

Что такое «стек»?

Стек — это такая структура данных, которая работает по принципу «Last In, First Out» (последним пришёл — первым ушёл). Таким образом, элемент «проталкивается» в стек и добавляется в его конец, а затем «выталкивается» из стека при удалении.

Стеки замечательны тем, что они очень быстрые. Большое «О» этого алгоритма равно O(1). Такая результативность объясняется тем, что при рекурсиях не используются циклы, вместо них используются функции pop() , push() и empty() .

Стоит ли использовать рекурсии вместо обычных циклов?

Оба этих метода одинаково эффективны для решения задач, однако выбор одного из них зависит от типа проблемы, поставленной перед вами.

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

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

Источник

BestProg

Рекурсия. Примеры рекурсивных методов (функций) в C#

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

Содержание

Поиск на других ресурсах:

1. Что такое рекурсия? Что такое рекурсивный метод (функция)?

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

Рекурсивный метод – это метод, который вызывает сам себя. В рекурсивном методе помещается вызов этого же метода по его имени.

Последовательный процесс рекурсивных вызовов метода подобен циклическому процессу.

⇑

2. Как работает рекурсивный вызов метода?

Если метод вызывает сам себя, то в памяти происходят следующие процессы:

• в системном стеке выделяется память для новых локальных переменных и параметров;
• программный код метода выполняется сначала с новыми локальными переменными и параметрами. Эти локальные переменные и параметры получают новые начальные значения. Сам программный код метода не копируется;
• при возврате из рекурсивного метода (оператор return ) происходит восстановление старых локальных переменных и параметров а также их значений в точке вызова этого метода.

⇑

3. Какие преимущества дает использование рекурсии в программах?

Рекурсию всегда сравнивают с итерацией. Для многих задач рекурсия дает следующие взаимосвязанные преимущества:

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

⇑

4. Какие недостатки использования рекурсии в программах?

В сравнении с итерационными вызовами, построение рекурсивных вызовов имеет следующие недостатки:

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

⇑

5. Пример вычисления суммы ряда

Разработать рекурсивную функцию вычисления суммы ряда

S = 5 + 10 + 15 + … + 5·n,

Программный код функции следующий

⇑

6. Пример конвертирования строки «AAABCCCCAADDDEF» => «3AB4C2A3DEF»

Данная задача очень удобно решается с помощью рекурсии. По данному образцу можно разрабатывать рекурсивные функции, которые обрабатывают строки по любым правилам.

В рекурсивной функции ConvertStr() рекурсивно просматривается вся строка. На каждом рекурсивном вызове обрабатывается один символ строки. В зависимости от позиции текущего обрабатываемого символа происходит соответствующий рекурсивный вызов функции.

Рекурсивная функция содержит следующие параметры:

• строка s типа string , которая обрабатывается;
• переменная, определяющая позицию символа в строке s на данном уровне рекурсии. Символ s[pos] имеет тип char ;
• целое число k , определяющее количество повторений символа s[pos] на данному уровне рекурсии;
• переменная c типа char , которая представляет символ на предыдущем уровне рекурсии. Это необходимо, так как символы, которые встречаются один раз подряд должны обрабатываться по особому.

Использование функции в другом программном коде

⇑

7. Пример сравнения строк

Разработать рекурсивную функцию, которая сравнивает две строки на идентичность. Две строки считаются идентичными, если:

• длина строк совпадает;
• совпадают символы каждой строки, которые находятся на одинаковых позициях.

Рекурсивная функция должна получать следующие параметры:

• ссылку на первую строку, которая сравнивается со второй строкой;
• ссылку на вторую строку, которая сравнивается с первой строкой;
• текущую позицию символов строк, которые сравниваются.

Функция должна возвращать результат типа bool . Если строки идентичны, то функция возвращает true , иначе функция возвращает false .

Использование функции в другом программном коде

⇑

8. Пример рекурсивной функции реверсирования строки

Программный код функции следующий

В функции RString() определение последнего символа в строке происходит по формуле:

Затем этот символ переводится в строку методом ToString() . Символ строки добавляется к следующему (предшествующему) символу в строке с помощью рекурсивного вызова

Поскольку функция должна что-то возвратить, то перед формулой обработки строки нужно вставить оператор return

Использование функции RString() в другом методе может быть следующим:

⇑

9. Пример рекурсивной функции определения, является ли строка симметричной

Разработать рекурсивную функцию, которая определяет есть ли симметричной часть строки s , начиная с i -го элемента и заканчивая j -м элементом

В вышеприведенной функции сравниваются символы, которые размещаются на позициях i+pos и j-pos строки с помощью оператора if

Параметр pos есть смещением, которое добавляется к значению i : i+pos . Между позициями i и j есть некоторые символы, которые формируют некоторый диапазон. Не нужно проходить параметром pos весь диапазон от i к j . Достаточно просмотреть только половину диапазона, поэтому функция содержит проверку:

есть середина диапазона (j-i) в соответствии с условием задачи.

Использование функции в другом программном коде

Источник

Как работает рекурсия – объяснение в блок-схемах и видео

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works — explained with flowcharts and a video.

«Для того чтобы понять рекурсию, надо сначала понять рекурсию»

Рекурсию порой сложно понять, особенно новичкам в программировании. Если говорить просто, то рекурсия – это функция, которая сама вызывает себя. Но давайте попробую объяснить на примере.

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

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

Есть два основных подхода в создании алгоритма для решения данной проблемы: итеративный и рекурсивный. Вот блок-схемы этих подходов:

Какой подход для Вас проще?

В первом подходе используется цикл while. Т.е. пока стопка коробок полная, хватай следующую коробку и смотри внутрь нее. Ниже немного псевдокода на Javascript, который отражает то, что происходит (Псевдокод написан как код, но больше похожий на человеческий язык).

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

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

Поскольку рекурсия используется во многих алгоритмах, очень важно понять как она работает. Если рекурсия до сих пор не кажется Вам простой, не беспокойтесь: Я собираюсь пройтись еще по нескольким примерам.

Граничный и рекурсивный случай

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

Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)

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

И снова функция подсчета, только уже с граничным случаем:

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

Сначала мы выведем цифру 5, используя команду Console.Log. Т.к. 5 не меньше или равно 1, то мы перейдем в блок else. Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).

Мы выведем цифру 4. И снова i не меньше или равно 1, так что мы переходим в блок else и передаем цифру 3. Это продолжается, пока i не станет равным 1. И когда это случится мы выведем в консоль 1 и i станет меньше или равно 1. Наконец мы зайдем в блок с ключевым словом return и выйдем из функции.

Стек вызовов

Рекурсивные функции используют так называемый «Стек вызовов». Когда программа вызывает функцию, функция отправляется на верх стека вызовов. Это похоже на стопку книг, вы добавляете одну вещь за одни раз. Затем, когда вы готовы снять что-то обратно, вы всегда снимаете верхний элемент.

Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1. Вот рекурсивная функция для подсчета факториала числа:

Теперь, давайте посмотрим что же происходит, когда вы вызываете fact(3). Ниже приведена иллюстрация в которой шаг за шагом показано, что происходит в стеке. Самая верхняя коробка в стеке говорит Вам, что вызывать функции fact, на которой вы остановились в данный момент:

Заметили, как каждое обращение к функции fact содержит свою собственную копию x. Это очень важное условие для работы рекурсии. Вы не можете получить доступ к другой копии функции от x.

Нашли уже ключ?

Давайте кратенько вернемся к первоначальному примеру поиска ключа в коробках. Помните, что первым был итеративный подход с использованием циклов? Согласно этому подходу Вы создаете стопку коробок для поиска, поэтому всегда знаете в каких коробках вы еще не искали.

Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!

И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!

Вы также можете посмотреть мое пятиминутное видео про рекурсию. Оно должно усилить понимание, приведенных здесь концепций.

Заключение от автора

Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием «Algorithms in Motion». И курс и статься написаны по замечательной книге «Grokking Algorithms», автором которой является Adit Bhargava, кем и были нарисованы все эти замечательные иллюстрации.

И наконец, чтобы действительно закрепить свои знания о рекурсии, Вы должны прочитать эту статью, как минимум, еще раз.

От себя хочу добавить, что с интересом наблюдаю за статьями и видеоуроками Beau Carnes, и надеюсь что Вам тоже понравилась статья и в особенности эти действительно замечательные иллюстрации из книги A. Bhargav «Grokking Algorithms».

Источник