Рекурсия или цикл что лучше
When to Loop? When to Recurse?
Как максимально использовать рекурсию в вашем коде.
По большей части концепции, приведенные в этой статье обсуждаются в контексте Python 3, но они также могут быть перенесены и на многие другие языки.
В книге Cracking the Coding Interview говорится, что “Все рекурсивные алгоритмы могут [также] быть реализованы итеративно…” в разделе, посвященном решению задач технического интервью с использованием рекурсии.
Итеративное решение проблемы на Python может включать использование циклов for или while. Это некоторые из наиболее распространенных инструментов, используемых для решения дополнительных задач на любом языке программирования.
Однако бывают случаи, когда итеративные решения могут превращаться в едва читаемые кошмары.
Попытка написать сильно вложенный и сложный код на доске с любопытным взглядом интервьюера, осматривающего вашу работу, может быть верным способом провалиться на техническом интервью.
Хотя переход от циклического подхода к рекурсивному не всегда сделает ваш код лучше, это отличный инструмент в вашу копилку.
Некоторое время я боялся изучать рекурсию. Узнав, что задачи рекурсивного подхода неизбежно имеют итеративную проблему, я зациклился на попытках решить все с помощью циклов.
Однако, по мере того как мои технические навыки росли, я столкнулся со многими проблемами LeetCode и HackerRank, которые требовали именно рекурсивного решения из-за их сложности. И пришло время расширить инструменты в моем распоряжении.
Что такое Циклы?
Цикл используется для выполнения повторяющегося блока кода столько раз, сколько необходимо для программы.
Для циклов, как в примере выше, итерация выполняется по последовательности. Обычно мы используем циклы for, когда знаем, сколько раз нам нужно выполнить блок кода. В приведенном выше примере нам нужно выполнить только вторую и третью строку кода для подсчета количества имен в name_list.
Возможно, нам также понадобится выполнить цикл неопределенное количество раз или пока определенное условие не будет выполнено. В таком случае нам пригодился бы цикл while.
Один из способов вернуть длину не повторяемого связанного списка (Linked List) — использование цикла while для обхода всех узлов, как в примере выше.
Хорошо, так что такое рекурсия?
Большая разница между рекурсивным и итеративным подходом заключается в том, что они по-разному заканчиваются. Пока цикл выполняет блок кода, каждый раз проверяя, находится ли он в конце своей последовательности, то у рекурсивного подхода такой проверки нет.
Как и в ужасном комиксе о Винни-Пухе, описанном выше, рекурсивная функция может продолжаться вечно, без каких-либо надежд избавиться от страданий.
Рекурсия, подобная приведенной выше, состоит из двух частей: рекурсивного вызова и базового случая.
Базовый случай (или иногда случаи) — это условие, которое проверяет, получили ли мы ту информацию, которая нам была нужна, из нашей функции. Каждая рекурсивная функция должна иметь хотя бы один базовый случай, однако их может быть и несколько.
В приведенном выше факториальном примере мы достигаем конца наших рекурсивных вызовов, когда достигаем числа 0.
Рекурсивный вызов — это когда функция вызывает себя, добавляясь в стек рекурсивного вызова.
Стеки являются объектами LIFO (Last In First Out), это означает, что последний элемент, который был добавлен в верхнюю часть стека, является первым, который будет удален из стека.
Когда я должен использовать рекурсию?
Рекурсия предназначена для решения проблем, которые можно разбить на более мелкие повторяющиеся задачи. Это особенно помогает при работе с вещами, которые имеют много возможных ветвей и слишком сложны для итеративного подхода.
Один хороший пример — выполнение поиска в файловой системе. Вы начинаете с корневой папки, а затем выполняете поиск по всему содержимому.
Рекурсия хорошо работает для данного типа структуры, потому что вы можете ищите различные пути ветвления без необходимости включать множество проверок и условий.
Как вы можете заметить, что изображение файловой системы выше очень похоже на древовидную структуру. Деревья и графики — это еще один случай, когда рекурсия — лучший и самый простой способ обхода.
Должен ли я всегда использовать рекурсию?
Рекурсия кажется действительно полезной! Может быть, я должен использовать этот подход все время?
Как и все, рекурсия лучше всего в дозах и желательно не слишком больших. Рекурсия — полезный инструмент, но он может увеличить использование памяти.
Итак, давайте вернемся к изображению факториального стека вызовов сверху. Каждый раз, когда мы добавляем новый вызов в стек, мы увеличиваем объем используемой памяти. Если проанализировать алгоритм, используя обозначение Big O, можем заметить, что это увеличивает потребление памяти в несколько раз по сравнению с итеративным подходом.
Однако иногда стоит пожертвовать памятью, чтобы получить короткий, полезный алгоритм, например, при обходе дерева. Но бывают и другие случаи, когда существует более лучшие и эффективные способы решения проблем.
Для большинства небольших проектов использование рекурсии, не сильно замедлит программу. Однако, как только ваша программа начинает делать много рекурсивных вызовов, то вам стоит рассмотреть потенциальное влияние данного подхода на производительность.
Еще одна вещь, которую следует учитывать, заключается в том, что понять и прочитать ваш код гораздо проще при итеративном подходе.
Использование рекурсии — это здорово, потому что она избавляет вас от множества дополнительных проблем.
Но когда вы пытаетесь полностью понять подзадачи, которые вы решаете, и то, как они решаются, то вам стоит реализовать итеративное решение. Если это неосуществимый маршрут, то, по крайней мере, попробуйте оптимизировать ваш рекурсивный подход, и углубить свои знания в этом направлении.
Какие реальные жизненные проблемы вы решили с помощью рекурсии? Дайте мне знать в ответах ниже!
Является ли рекурсия быстрее, чем зацикливание?
Я знаю, что рекурсия иногда намного чище, чем зацикливание, и я ничего не спрашиваю о том, когда мне следует использовать рекурсию поверх итерации, я знаю, что уже есть много вопросов по этому поводу.
Что я спрашиваю, так ли рекурсия всегда быстрее, чем цикл? Мне кажется, вы всегда сможете уточнить цикл и заставить его работать быстрее, чем рекурсивная функция, потому что цикл отсутствует, постоянно настраивая новые кадры стека.
Я специально ищу, является ли рекурсия быстрее в приложениях, где рекурсия является правильным способом обработки данных, например, в некоторых функциях сортировки, в двоичных деревьях и т. Д.
Это зависит от используемого языка. Вы написали «независимый от языка», поэтому я приведу несколько примеров.
В Java, C и Python рекурсия довольно дорога по сравнению с итерацией (в целом), потому что она требует выделения нового фрейма стека. В некоторых C-компиляторах можно использовать флаг компилятора, чтобы устранить эти издержки, которые преобразуют определенные типы рекурсии (фактически, определенные типы хвостовых вызовов) в переходы вместо вызовов функций.
Я знаю, что в некоторых реализациях Scheme рекурсия, как правило, будет быстрее, чем зацикливание.
Короче говоря, ответ зависит от кода и реализации. Используйте любой стиль, который вы предпочитаете. Если вы используете функциональный язык, рекурсия может быть быстрее. Если вы используете императивный язык, итерация, вероятно, быстрее. В некоторых средах оба метода приводят к созданию одной и той же сборки (поместите ее в свою трубу и выкурите ее).
рекурсия всегда быстрее, чем цикл?
Нет, Итерация всегда будет быстрее, чем Рекурсия. (в архитектуре фон Неймана)
Объяснение:
Если вы создаете минимальное количество операций с обычного компьютера с нуля, «Итерация» стоит на первом месте в качестве строительного блока и требует меньше ресурсов, чем «рекурсия», следовательно, это быстрее.
Создание псевдо-вычислительной машины с нуля:
Задайте себе вопрос : что вам нужно, чтобы вычислить значение, то есть следовать алгоритму и достичь результата?
Мы создадим иерархию понятий, начиная с нуля и определяя в первую очередь базовые, основные понятия, затем создадим понятия второго уровня с ними и так далее.
а) Установить и переместить ячейки памяти
б) логика и арифметика
Выражение выше подразумевает 3 шага с неявной переменной «result».
Указатель инструкций : если у вас есть последовательность шагов, у вас также есть неявный «указатель инструкций». Указатель инструкции отмечает следующую инструкцию и продвигается после чтения инструкции, но до ее выполнения.
Бесконечная итерация : отскочив назад, теперь вы можете заставить агента «повторить» определенное количество шагов. На данный момент у нас есть бесконечная итерация.
Реализация: (новые концепции не требуются)
Проблема с одноуровневой реализацией: Вы не можете вызвать другую подпрограмму из подпрограммы. Если вы это сделаете, вы перезапишете возвращающий адрес (глобальную переменную), поэтому вы не сможете вкладывать вызовы.
Чтобы иметь лучшую реализацию для подпрограмм: вам нужен STACK
Стек : Вы определяете пространство памяти для работы в качестве «стека», вы можете «выталкивать» значения в стек, а также «выталкивать» последнее «вытолкнутое» значение. Для реализации стека вам понадобится указатель стека (подобный указателю инструкций), который указывает на фактическую «верхушку» стека. Когда вы «нажимаете» значение, указатель стека уменьшается, и вы сохраняете значение. Когда вы «выталкиваете», вы получаете значение в фактическом указателе стека, а затем увеличивается указатель стека.
Рекурсия : что происходит, когда подпрограмма вызывает себя? Это называется «рекурсия».
Проблема: Перезаписывая локальные промежуточные результаты, подпрограмма может быть сохранена в памяти. Поскольку вы вызываете / повторно используете одни и те же шаги, если промежуточный результат хранится в предопределенных ячейках памяти (глобальных переменных), они будут перезаписаны при вложенных вызовах.
Достигнув рекурсии, мы останавливаемся здесь.
Вывод:
Итерация всегда будет быстрее в машинном коде, потому что она подразумевает меньше инструкций и, следовательно, меньше циклов ЦП.
Какой лучше»?
Вам следует использовать «итерацию», когда вы обрабатываете простые последовательные структуры данных, и везде будет работать «простой цикл».
Вы должны использовать «рекурсию», когда вам нужно обработать рекурсивную структуру данных (мне нравится называть их «фрактальными структурами данных»), или когда рекурсивное решение явно более «элегантно».
Совет : используйте лучший инструмент для работы, но понимайте внутреннюю работу каждого инструмента, чтобы выбирать мудро.
Рекурсия может быть быстрее, если альтернативой является явное управление стеком, как в алгоритмах сортировки или двоичного дерева, о которых вы упомянули.
У меня был случай, когда переписывание рекурсивного алгоритма в Java сделало его медленнее.
Таким образом, правильный подход заключается в том, чтобы сначала написать его наиболее естественным образом, оптимизировать только в том случае, если профилирование показывает его критичность, а затем измерить предполагаемое улучшение.
Рекурсия vs циклы
я сталкиваюсь с проблемой, когда и рекурсия, и использование цикла кажутся естественными решениями. Существует ли соглашение или» предпочтительный метод » для таких случаев? (Очевидно, это не так просто, как показано ниже)
рекурсия
15 ответов
Я предпочитаю рекурсивные решения, когда:
реализация рекурсии намного проще, чем итерационное решение, обычно потому, что она использует структурный аспект проблемы таким образом, что итеративный подход не может
Я могу быть разумно уверен, что глубина рекурсии не вызовет переполнения стека, предполагая, что мы говорим о языке, который реализует рекурсию это путь
Условие 1, похоже, здесь не так. Итеративное решение примерно такого же уровня сложности, поэтому я бы придерживался итеративного маршрута.
Если производительность имеет значение, то проверьте оба и выберите на рациональной основе. Если нет, то выберите на основе сложности, с беспокойством о возможном переполнении стека.
есть руководство из классической книги элементы стиля программирования (Kernighan и Plauger) этот алгоритм должен следовать структуре данных. То есть рекурсивные структуры часто обрабатываются более четко с помощью рекурсивных алгоритмов.
рекурсия используется для выражения алгоритма, который естественно рекурсивен в более понятной форме. «Естественно рекурсивный» алгоритм-это тот, где ответ строится из ответов на более мелкие подзадачи, которые, в свою очередь, строятся из ответов на еще более мелкие подзадачи и т. д. Например, вычисление факториала.
в языке программирования, который не является функциональным, итеративный подход почти всегда быстрее и эффективнее, чем рекурсивный подход, поэтому причина использования рекурсии-ясность, а не скорость. Если рекурсивная реализация заканчивается меньше ясно, чем итеративная реализация, то всеми средствами избежать этого.
в этом конкретном случае я бы решил, что итеративная реализация будет более ясной.
Если вы используете функциональный язык (похоже, это не так), перейдите к рекурсии. Если нет, цикл, вероятно, будет лучше понят кем-либо еще, работающим над проектом. Конечно, некоторые задачи (например, рекурсивный поиск в каталоге) лучше подходят для рекурсии, чем другие.
кроме того, если код не может быть оптимизирован для конечной рекурсии, цикл безопаснее.
используйте цикл. Это легче читать и понимать (чтение кода всегда намного сложнее, чем его написание), и, как правило, намного быстрее.
Я предпочитаю петли как
Я использую стеки (схема LIFO), чтобы заставить циклы работать
в java стеки покрыты интерфейсом Deque
менее сложный, более компактный, чем
последний имеет меньше кода, но две функции и труднее понять код, ПО МОЕМУ.
Я бы сказал, что версия рекурсии лучше понятна, но только с комментариями:
гораздо проще объяснить эту версию. Попробуйте написать хороший комментарий к версии цикла, и вы увидите.
доказуемо, что все хвостовые рекурсивные алгоритмы могут быть развернуты в цикл, и наоборот. Вообще говоря, рекурсивная реализация рекурсивного алгоритма более понятна для программиста, чем реализация цикла, а также легче отлаживается. Также, вообще говоря, реальная производительность реализации цикла будет быстрее, так как ветвь/прыжок в цикле обычно выполняется быстрее, чем нажатие и выскакивание кадра стека.
лично говоря, для хвостовых рекурсивных алгоритмов я предпочитаю придерживаться рекурсивной реализации во всех, кроме наиболее интенсивных ситуаций.
Я нахожу рекурсию более естественной, но вы можете быть вынуждены использовать цикл, если ваш компилятор не выполняет оптимизацию хвостового вызова, а ваше дерево/список слишком глубоки для размера стека.
Я обычно предпочитаю использовать петли. Большинство хороших проектов ООП позволят вам использовать циклы без использования рекурсии (и, таким образом, остановить программу от нажатия всех этих неприятных параметров и адресов в стек).
Он больше используется в процедурном коде, где кажется более логичным думать рекурсивно (из-за того, что вы не можете легко хранить состояние или метаданные (информация?) и, таким образом, вы создаете больше ситуаций, которые заслуживают использовать.)
рекурсия хороша для прото-ввода функции и / или написания базы, но после того, как вы знаете, что код работает, и вы возвращаетесь к нему на этапе оптимизации, попробуйте заменить его циклом.
опять же, это все упрямый. Делай то, что лучше для тебя.
Если ваш код скомпилирован, это, вероятно, мало что изменит. Проведем небольшой тест и посмотреть, сколько памяти используется и как быстро она работает.
Если система, над которой вы работаете, имеет небольшой стек (встроенные системы), глубина рекурсии будет ограничена, поэтому будет желательно выбрать алгоритм на основе цикла.
вы также можете написать цикл в более удобочитаемом формате. С for(init;while;increment) имеют некоторые недостатки читаемости, так как описанное в начале, но выполняется в конце цикла.
вот образцы, измененные (и предполагая, что null false)
рекурсия (фиксированный и хвост-вызов оптимизируется)
Ну я видел тонны ответов, и даже принял ответ, но никогда не видел и думал, почему.
всегда избегайте рекурсий, если вы можете сделать тот же блок, который будет производиться циклами!
как работает рекурсия?
• кадр в памяти стека выделяется для одного вызова функции
• рамка содержит ссылку на фактическое метод
• если метод имеет объекты, объекты помещаются в память кучи, а фрейм будет содержать ссылку на эти объекты в памяти кучи.
•эти шаги выполняются для каждого отдельного вызова метода!
риски :
• StackOverFlow, когда стек не имеет памяти для размещения новых рекурсивных методов.
* OutOfMemory, когда куча не имеет памяти для размещения рекурсивных хранимых объектов.
Как цикл работы?
• все предыдущие шаги, за исключением того, что выполнение повторно кода внутри цикла не будет потреблять никаких дополнительных данных, если они уже потреблены.
риски :
• одиночный риск внутри пока петля когда ваше условие как раз никогда не будет существовать. Ну, это не вызовет сбоев или что-то еще, он просто не выйдет из цикла, если вы наивно это сделаете while(true) 🙂
избежать рекурсии. Скорее всего, в какой-то момент часть кода придется поддерживать, и будет проще, если это не будет сделано с рекурсией. Во-вторых, у него, скорее всего, будет более медленное время выполнения.
Циклы рекурсии или пока
Я читал о некоторых практиках интервью для разработчиков, в частности о технических вопросах и тестах, которые задавались на собеседованиях, и я несколько раз спотыкался о высказываниях жанра: «Хорошо, вы решили проблему с помощью цикла while, теперь вы можете сделать это с помощью рекурсия «, или» каждый может решить это с помощью цикла из 100 строк, но может ли он сделать это с помощью рекурсивной функции из 5 строк? » и т.п.
Мой вопрос, является ли рекурсия вообще лучше, чем если / while / for конструкции?
Я, честно говоря, всегда думал, что рекурсия не является предпочтительной, потому что она ограничена стековой памятью, которая намного меньше, чем куча, и выполнение большого количества вызовов функций / методов является неоптимальным с точки зрения производительности, но я могу быть неправым.
Другое соображение заключается в том, что итеративные циклы требуют деструктивных обновлений состояния, что делает их несовместимыми с чистой (без побочных эффектов) семантикой языка. Это причина того, что чистые языки, такие как Haskell, вообще не имеют циклических конструкций, а во многих других языках функционального программирования их либо нет, либо они избегают их в максимально возможной степени.
Если во время интервью вы получите такой вопрос, это хороший знак: это означает, что потенциальный работодатель ищет людей, которые могут программировать, а не людей, которые запомнили руководство по инструменту программирования.
Рекурсия и цикл, в чем разница? На примере Python
Цикл — это фундаментальный инструмент в программировании. Существует множество различных типов циклов, но почти все они выполнят одну базовую функцию: повторение определённых действий над данными, для их анализа или управления ими. Рекурсия, так же распространённый способ анализировать и манипулировать данными, как и цикл, но как правило, менее понятный и часто более запутанный. Почти все рекурсивные функции можно переписать в циклы, и наоборот. Тем не менее, каждый тип функции имеет свои преимущества и недостатки, и сегодня вы узнаете, в каких случаях применять тот или иной метод. В статье мы разберём следующие вопросы:
Начнём с метода, который кажется более простым из этих двух.
Циклы for
Цикл for используют для перебора последовательности данных (списка, кортежа, словаря, набора или строки). При достижении конца последовательности цикл завершается.
Например, вам нужно сложить числа от 1 до 5 и получить их сумму. Конечно, вы можете просто суммировать 1+2+3+4+5. Но, создать функцию намного удобнее, потому что вы сможете использовать её повторно, причём подставляя любые значения, даже если они не известны заранее.
Это будет выглядеть примерно так:
Для работы такого цикла, нам нужно хранить список всех чисел, чтобы мы могли перебирать элементы и складывать их в итоговое значение.
Вот как это выглядит в коде:
Запустив код, мы увидим, что все числа на своих местах и нам возвращается их сумма.
Вывод функции:
Рекурсия
Если функция вызывает сама себя, то это является признаком рекурсии. Одно из важнейших отличий рекурсии от цикла, это способ завершения рекурсивной функции. В приведённом выше примере цикл for завершается в конце последовательности, в которой он выполняется. А вот рекурсивная функция может продолжаться бесконечно, потому что она может не иметь последовательности данных. Вместо этого у рекурсивной функции есть так называемое базовое условие. Базовое условие определяет, когда цикл должен завершится.
Давайте попробуем решить предыдущую задачу рекурсивным способом. Визуально это выглядит так:
Каждый раз функция либо вызывает себя с новыми входными данными, либо возвращает значение.
Вот как это выглядит в коде:
Как видите мы передаём два значения: начальное и итоговое. При первом вызове функции итоговое значение равно 0, а начальное 5. Мы проверяем, является ли начальное число 0. Если нет, то вызываем функцию снова, но на этот раз мы меняем входное значение на 5–1 и 0+5, и повторяем этот процесс до тех пор, пока n не будет равно 0. После выполнения этого условия мы возвращаем итоговое значение (15).
Вычисление сложного процента рекурсией и циклом FOR
Давайте разберём более сложную задачу. Нужно определить стоимость кредита или инвестиции со сложным процентом. Чтобы это сделать, нам нужны следующие данные:
Формула расчёта сложного процента:
Так мы можем рассчитать всю сумму сразу. Но вместо этого, для расчёта мы используем цикл или рекурсию. В таком случае переменная времени (nt) будет обрабатываться в итерациях.
Давайте сразу создадим переменные, в которых будем хранить исходные числа и используем их в обоих методах:
Расчёт по сложной процентной ставке итеративно
Давайте сразу посчитаем общее количество платежей, чтобы упростить вычисление в цикле. Так как платежи ежемесячные, а количество лет равно 10, то результат будет 120, или 10*12. Теперь мы можем вычислять процент для каждого месяца и добавлять результат каждой итерации к основной сумме.
Так выглядит код:
Единственное различие между этим и предыдущим примерами заключается в том, что мы делаем на несколько вычислений больше во время каждой итерации. Также увеличилось число итераций с 5 до 120.
Результат наших вычислений:
Расчёт по сложной процентной ставке рекурсивным способом
В предыдущем примере последовательность данных равна 120, что отражает количество раз, когда основная сумма пересчитывается. Цикл прерывается по завершении последовательности. Рекурсивный метод позволяет нам поступить схожим образом, т.е. инициализировать счётчик и задать два условия.
Выполнить вычисление сложного процента. Добавить результат вычисления к общей сумме. Уменьшить значение счётчика на 1. Повторить те же действия, подставив новое значения для счётчика и общей суммы.
Возврат общей суммы
В предыдущем примере, цикл функции начинался со значения 5 и завершался при 0.
Здесь происходит тоже самое, только начальное значение теперь 120
Здесь мы либо снова вызываем функцию, либо возвращаем обновлённую общую сумму. Каждый раз вызывая функцию, значение счётчика уменьшается на 1. Возврат общей суммы происходит, когда счётчик равен 0.
Когда использовать рекурсию
Выбор между рекурсивным и итеративным методом может в значительной степени зависеть от языка, который вы используете, или от задачи, которую вы намерены решить. Например, в JavaScript рекурсия может привести к ошибкам stack frame errors, когда предел стека уже достигнут, а базовое условие ещё не выполнено. В таком случае, итеративный подход будет работать лучше.
Рассмотренный выше случай является хорошим примером того, когда рекурсия работает намного лучше, чем цикл.
Давайте представим, что помимо тех чисел, которые мы использовали в предыдущем примере, нам нужно учитывать и другие данные. Например, мы можем отслеживать то, как регулярные платежи влияют на срок кредита. Возможно, мы захотим остановить цикл до завершения последовательности. Если общее количество раз, когда начисляются проценты по кредиту равно 120, то и длина списка равна 120. Но, если сумма кредита будет равна 0 уже после 100 итераций, то в конце списка останется 20 неиспользуемых и ненужных элементов списка. Проблема дальнейшего усложнения сценария цикла заключается в том, что значения переменных, таких как сумма кредита, зависит от значения той же переменной на предыдущей итерации. Дело не в том, что это сложно реализовать, а в том, что это грязно.
Визуализация данной проблемы:
Рекурсивные структуры данных
Именно в таких случаях рекурсивные структуры данных особенно полезны. Структуру можно назвать рекурсивной, если её можно определить в терминах меньшей версии самой себя. Список является примером рекурсивной структуры данных.
Например, возьмём такой список:
Теперь, сделаем на его основе два меньших списка:
Если вывести оба списка, то мы увидим следующее:
Благодаря рекурсивным функциям и рекурсивными структурам данных мы можем изменить весь список или меньшую часть большего списка за раз. Итеративный подход решения подобной проблемы, позволяет изменить только одно значение в одном индексе за раз.
Пример того, как это сделать:
Сохранив маленькие части большого списка, мы можем вызвать ту же функцию (рекурсия) и отправить ей эти части (рекурсивная структура данных).
Вот как это работает на примере с вычислением сложного процента:
Наша функция в основном состоит из операторов if и else. Мы можем усложнить эту структуру если понадобится, но она и в таком виде делает всё что нам нужно. В итоге, мы хотим вернуть окончательные данные, которые покажут нам сумму кредита и размер текущего платежа на каждой итерации, когда начисляется процент.
Выходные данные:
Визуализация процессов рекурсивной функции:
При каждом рекурсивном вызове мы будем брать первый элемент массива из списка. Затем мы изменим значения этого элемента и снова вызовем функцию, но на этот раз передадим ей в качестве параметров array[:1] и array[1:]. На картинке видно, что, достигнув середины списка, мы будем иметь две его части одинакового размера. А уже к концу мы полностью переберём и модифицируем все элементы первого списка, и добавим их во второй список. Далее мы шаг за шагом реализуем эту функцию в коде.
Шаг 1: создаём массив
На данном этапе, наш массив имеет длину равную числу раз, когда начисляется процент. Каждый элемент содержит одинаковые данные, которые мы будем изменять рекурсивно.
Шаг 2: создаём функцию и базовое условие
Базовое условие будет учитывать два возможных сценария. Либо счётчик достигнул конца последовательности ( len(inputArr) == 0 ), либо мы погасили кредит раньше ( inputArr[-1][‘principal amount’] ).
Шаг 3: создаём выражение else и определяем переменные current, inputArray и outputArray
Шаг 4: если массив outputArray пуст, то берём первый элемент из массива входных данных и помещаем его в массив выходных данных без изменений.
Теперь оба массива выглядят как на картинке, которую вы видели выше, в момент первого вызова рекурсивной функции.
Шаг 5: если массив выходных данных не пуст, то изменяем все значения текущего элемента.
Шаг 6: добавляем переменную newCurrent к массиву outputArray
Шаг 7: вызываем рекурсивную функцию с новыми параметрами
Мы закончили! Так выглядит код целиком:
Чтобы убедиться, что код работает так, как мы задумали, давайте увеличим сумму платежа.
Если изменить сумму платежа на 2000, то при выводе должны получиться такие данные:
Такой код возвращает более чистый результат, чем при использовании цикла. Если бы мы использовали итеративный подход, то нам пришлось бы перебрать все 120 элементов, большинство из которых были бы бесполезны/пусты.
Заключение
На первый взгляд рекурсия может показаться сложной. Но в некоторых случаях, рекурсивный метод невероятно эффективен, если всё сделать правильно. Тем не менее, иногда лучше использовать циклы. Понимание обоих методов и умение эффективно их использовать поможет вам в работе и будет преимуществом на собеседовании.