Не бойтесь рекурсии

Не бойтесь рекурсии

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

Чтобы понять рекурсию, вы должны понять рекурсию.

Но сначала давайте определим, что такое рекурсия, а потом посмотрим, как создать красивую рекурсивную и функциональную функцию в вашем коде.

Что такое рекурсия

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

Наша функция имеет целью напечатать переданный char в качестве аргумента. И после того, как напечатайте его, вызовите себя.

По сути, это точный перевод на язык C нашей функции. Теперь давайте посмотрим, что произойдет, когда мы запустим его в основную функцию.

Конечно, когда вы пробуете рекурсию в первый раз, вывод функции может быть похож на то, что вы сказали, когда запускали свою первую рекурсивную функцию. Но почему она никогда не перестанет печатать «A» в терминале?
Чтобы объяснить это, функция будет вызывать себя бесконечное количество раз и никогда не останавливаться. Это вызовет некоторую ошибку, которая увидит следующую часть.

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

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

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

Итак, давайте создадим счет от 10 до 0 (мы попробуем использовать рекурсивный случай)

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

Итак, как видите, мы получили хороший результат, но не такой, как ожидали. Цель состояла в том, чтобы создать счетную форму от 10 до 0, и мы застряли в бесконечном цикле. Итак, что касается циклов for или while, нам нужно дать функции оператор, чтобы сказать, когда остановиться. Этот случай называется базовым.

Базовый вариант

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

Поздравляю! Вы создали свою первую рекурсивную функцию.

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

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

Стек вызовов

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

Итак, прежде чем рассматривать стек вызовов, давайте быстро напомним предыдущую часть и посмотрим, где наши два разных случая.
Первый, рекурсивный случай, когда функция вызывает саму себя, мощность x уменьшите на единицу, если оно положительное, или увеличьте на единицу, если оно отрицательное. Таким образом, каждый раз, когда функция вызывает сама себя, она выполняет другую и полезную работу для «родительской» функции.
Второй, базовый случай, когда мощность равна 0. Итак, если мы возьмем 3 степени 0 , он равен 1, поэтому функция возвращает 1.

Итак, у нас есть все элементы, чтобы получить идеальную и работающую рекурсивную функцию! Большой! В качестве примера этой функции, учитывая 2, 4 в качестве аргумента, окончательный возврат будет 16.

Но то, как это работает, не так просто, как функция подсчета, которую мы сделали ранее! И пришло время осветить стек вызовов. Эта концепция очистит ваш разум и сделает вас профессионалом рекурсии.

Стек, если вы не знакомы с этой структурой данных, похож на очередь ожидания в реальной жизни, только наоборот. Он работает за кулисами вашего компьютера, и у вас нет никакой информации о том, что он делает. Поэтому важно понимать, как это работает.
Каждый раз, когда вы вводите элемент в стек, когда новый парень встает в очередь ожидания, он будет последним в очереди, и если мы будем следовать этому примеру, первый парень, который встал в очередь, будет первым на кассе. Таким образом, эта концепция является концепцией очереди в информатике. Первым прибыл - первым обслужен Эквивалент в русском языке: поздний гость гложет и кость. Но стек работает немного иначе, чем очередь, в обратном порядке. Последний пришел, первый обслужен.
Таким образом, каждый раз, когда вы добавляете функцию для обработки в стек, эта функция будет обрабатываться в первый раз, затем следующая функция и т. д. Может быть сложно понять концепцию на словах, но давайте возьмем пример. с нашей функцией.
x будет 2, а y будет 4.

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

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

Сначала идём по синей дороге, а потом по красной (то же самое на второй схеме).

Теперь вы можете освоить концепцию отказа. Если вам нужен какой-то другой пример, вот видео от Gayle Laakmann Mcdowell, а также вы можете заглянуть в замечательную книгу Алгоритмы грокинга от Aditya Y.Bahrgav. Эти два ресурса могут дополнить все ваши знания о рекурсии.

Тогда может возникнуть вопрос, зачем использовать рекурсию, когда мы можем сделать это только с помощью циклов for или while, например, пройти через метод итерации.

Рекурсия против итерации

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

Функция рекурсии полезна для создания простейшего способа решения проблем или его визуализации, например, алгоритмов разделяй и властвуй, чего не может сделать итерация. Поэтому наилучшей практикой в ​​этом случае является создание рекурсивных функций.
Вот несколько алгоритмов сортировки, которые их используют.
Быстрая сортировка раздела Ломуто
Быстрая сортировка раздела Хоара
Битоник Сорт

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

Заключение

Поздравляю! Вы становитесь профессионалом рекурсии, теперь вам просто нужно приложить руку, закодировать некоторые рекурсивные функции, такие как факториал и другие, чтобы быть большим боссом в этом.
Удачного дня, увидимся в следующей статье. ;)