Что быстрее рекурсия или цикл

Является ли рекурсия быстрее, чем зацикливание?

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

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

Я специально ищу, является ли рекурсия быстрее в приложениях, где рекурсия является правильным способом обработки данных, например, в некоторых функциях сортировки, в двоичных деревьях и т. Д.

Это зависит от используемого языка. Вы написали «независимый от языка», поэтому я приведу несколько примеров.

В Java, C и Python рекурсия довольно дорога по сравнению с итерацией (в целом), потому что она требует выделения нового фрейма стека. В некоторых C-компиляторах можно использовать флаг компилятора, чтобы устранить эти издержки, которые преобразуют определенные типы рекурсии (фактически, определенные типы хвостовых вызовов) в переходы вместо вызовов функций.

Я знаю, что в некоторых реализациях Scheme рекурсия, как правило, будет быстрее, чем зацикливание.

Короче говоря, ответ зависит от кода и реализации. Используйте любой стиль, который вы предпочитаете. Если вы используете функциональный язык, рекурсия может быть быстрее. Если вы используете императивный язык, итерация, вероятно, быстрее. В некоторых средах оба метода приводят к созданию одной и той же сборки (поместите ее в свою трубу и выкурите ее).

рекурсия всегда быстрее, чем цикл?

Нет, Итерация всегда будет быстрее, чем Рекурсия. (в архитектуре фон Неймана)

Объяснение:

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

Создание псевдо-вычислительной машины с нуля:

Задайте себе вопрос : что вам нужно, чтобы вычислить значение, то есть следовать алгоритму и достичь результата?

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

а) Установить и переместить ячейки памяти

б) логика и арифметика

Выражение выше подразумевает 3 шага с неявной переменной «result».

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

Бесконечная итерация : отскочив назад, теперь вы можете заставить агента «повторить» определенное количество шагов. На данный момент у нас есть бесконечная итерация.

Реализация: (новые концепции не требуются)

Проблема с одноуровневой реализацией: Вы не можете вызвать другую подпрограмму из подпрограммы. Если вы это сделаете, вы перезапишете возвращающий адрес (глобальную переменную), поэтому вы не сможете вкладывать вызовы.

Чтобы иметь лучшую реализацию для подпрограмм: вам нужен STACK

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

Рекурсия : что происходит, когда подпрограмма вызывает себя? Это называется «рекурсия».

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

Достигнув рекурсии, мы останавливаемся здесь.

Вывод:

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

Какой лучше»?

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

Вы должны использовать «рекурсию», когда вам нужно обработать рекурсивную структуру данных (мне нравится называть их «фрактальными структурами данных»), или когда рекурсивное решение явно более «элегантно».

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

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

У меня был случай, когда переписывание рекурсивного алгоритма в Java сделало его медленнее.

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

Источник

Рекурсия когда-либо быстрее, чем цикл?

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

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

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

12 ответов

Это зависит от используемого языка. Вы написали «язык-агностик», поэтому я приведу несколько примеров.

в Java, C и Python рекурсия довольно дорога по сравнению с итерацией (в целом), потому что она требует выделения нового кадра стека. В некоторых компиляторах C можно использовать флаг компилятора для устранения этих накладных расходов, который преобразует определенные типы рекурсии (фактически, определенные типы хвостовых вызовов) в Прыжки вместо вызовов функций.

In реализации функционального языка программирования, иногда итерация может быть очень дорогой, а рекурсия может быть очень дешевой. Во многих рекурсия преобразуется в простой прыжок, но изменение переменной цикла (которая является изменяемой) иногда требует некоторых относительно тяжелых операций, особенно на реализациях, которые поддерживают несколько потоков выполнения. Мутация стоит дорого в некоторых из этих сред из-за взаимодействия между мутатором и мусором коллектор, если оба могут работать одновременно.

Я знаю, что в некоторых реализациях схема рекурсия обычно будет быстрее, чем цикл.

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

дополнение: в некоторых средах лучшей альтернативой является не рекурсия и не итерация, а функции более высокого порядка. К ним относятся «карта», «фильтр» и «уменьшить»(который также называется «сгиб»). Они не только являются предпочтительным стилем, не только они часто чище, но в некоторых средах эти функции являются первыми ( или только), чтобы получить импульс от автоматического распараллеливания-так они могут быть значительно быстрее, чем итерация или рекурсия. Примером такой среды является Data Parallel Haskell.

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

рекурсия когда-либо быстрее, чем цикл?

нет, итерация всегда будет быстрее, чем рекурсия. (в архитектуре фон Неймана)

объяснение:

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

построение псевдо-вычислительной машины с нуля:

вопрос: что вам нужно вычислить значение, т. е. следовать алгоритму и достичь результата?

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

Первая Концепция: ячейки памяти, хранение, состояние. Делать то, что вы нужно мест для хранения конечных и промежуточных результирующих значений. Предположим, у нас есть бесконечный массив «целочисленных» ячеек, называемых , M[0..Бесконечный.]

инструкции: сделайте что-нибудь-преобразуйте ячейку, измените ее значение. изменить состояние. Каждая интересная инструкция выполняет преобразование. Основные инструкции:

a) установить и переместить ячейки памяти

b)логика и арифметика

порядок шагов: последовательность инструкций: т. е.: сделайте это сначала, сделайте это после и т. д. Императивная последовательность инструкций. Даже одну строчку!—11—>выражения являются «императивной последовательностью инструкций». Если у вас есть выражение с определенным «порядком оценки» у вас есть шаги. Это означает, что даже одно составленное выражение имеет неявные «шаги», а также имеет неявную локальную переменную (назовем ее»результат»). например:

приведенное выше выражение подразумевает 3 шага с неявной переменной «результат».

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

Инструкция Указатель: если у вас есть последовательность шагов, у вас также есть неявный «указатель инструкции». Указатель инструкции отмечает следующую инструкцию и продвигается после чтения инструкции, но до выполнения инструкции.

в этой псевдо-вычислительной машине указатель инструкции является частью . (Примечание: обычно Инструкция Указатель будет «специальный регистр» в ядре процессора, но здесь мы упростим понятия и предположим, что все данные (включая регистры) являются частью «памяти»)

Бесконечные Итерации: By прыжки назад, теперь вы может заставить агента «повторить» определенное количество шагов. На данный момент у нас есть бесконечные итерации.

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

наименования: давать имена к определенному положению памяти держа данные или держа шаг. Это просто «удобство». Мы не добавляем никаких новых инструкций, имея возможность определить «имена» для участков памяти. «Именование» не является инструкцией для агента, это просто удобство для нас. наименования делает код (на данный момент) легче читать и легче изменить.

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

реализация: (не требуется никаких новых концепций)

иметь лучшая реализация для подпрограмм: Вам нужен стек

стек: вы определяете пространство памяти для работы как «стек», вы можете» нажать «значения в стеке, а также» поп «последнее» нажатое » значение. Для реализации стека вам понадобится Указатель Стека (аналогично указателю инструкции), который указывает на фактическую «головку» стека. Когда вы» нажимаете » значение, указатель стека уменьшается, и вы сохраняете значение. Когда вы «поп», вы получаете значение на фактический указатель стека, а затем указатель стека увеличивается.

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

рекурсия: что происходит, когда подпрограмма вызывает себя?. Это называется «рекурсия».

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

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

достиг рекурсия мы останавливаемся здесь.

вывод:

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

какой из них «лучше»?

вы должны использовать «итерацию», когда вы обрабатываете простой, последовательные структуры данных, и везде «простой цикл» будет делать.

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

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

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

У меня был случай, когда переписывание рекурсивного алгоритма на Java сделало его медленнее.

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

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

рассмотрим, что абсолютно необходимо сделать для каждого, итерации и рекурсии.

вы видите, что здесь не так много места для различий.

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

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

TL;DR рекурсивные алгоритмы обычно имеют худшее поведение кэша, чем итеративные.

большинство ответов здесь неправильно. Правильный ответ:зависит. Например, вот две функции C, которые проходят через дерево. Сначала рекурсивный:

и вот та же функция, реализованная с помощью итерации:

не важно понимать детали кода. Вот именно!—2—> узлы и P_FOR_EACH_CHILD не ходить. В итеративной версии нам нужен явный стек st на какие узлы нажимаются, а затем выскакивают и манипулируют.

в первом случае у вас есть только рекурсивные CALL для каждого узла.

кроме того, доступ к переменным в callstack невероятно быстрый. Это означает, что Вы читаете по памяти, которая вероятно, всегда будет в самом сокровенном тайнике. С другой стороны, явный стек должен поддерживаться malloc :ed память из кучи, которая намного медленнее для доступа.

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

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

функциональное программирование больше о»что» вместо «как«.

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

но, что более важно с точки зрения программиста-это читаемость и ремонтопригодность, а не оптимизация в первую место. Опять же, «преждевременная оптимизация-это корень всех зол».

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

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

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

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

согласно теории это то же самое. Рекурсия и цикл с той же сложностью O() будут работать с той же теоретической скоростью, но, конечно, реальная скорость зависит от языка, компилятора и процессора. Пример с мощностью числа может быть закодирован итерационным способом с помощью O (ln (n)):

Источник

Рекурсия и цикл, в чем разница? На примере 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 элементов, большинство из которых были бы бесполезны/пусты.

Заключение

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

Источник