Рекурсивный алгоритм это кратко

Обновлено: 07.07.2024

Рекурсия — это свойство объекта подражать самому себе. Объект является рекурсивным если его части выглядят также как весь объект. Рекурсия очень широко применяется в математике и программировании:

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

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

    Содержание:

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

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

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

    Поиск элемента массива

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

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

    Двоичный поиск в массиве

    Вычисление чисел Фибоначчи

    Числа Фибоначчи определяются рекуррентным выражением, т.е. таким, что вычисление элемента которого выражается из предыдущих элементов: \(F_0 = 0, F_1 = 1, F_n = F_ + F_, n > 2\).

    Быстрая сортировка (quick sort)

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

    рис. 1 блок-схема алгоритма быстрой сортировки

    Блок-схема алгоритма быстрой сортировки

    Сортировка слиянием (merge sort)

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

    merge-sort_flowchart

    Блок схема сортировки слиянием

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

    Анализ рекурсивных алгоритмов

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

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

    Метод подстановки (итераций)

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

    Можно предположить, что \(T^_n = T^_ + k\times\mathcal(1)\), но тогда \(T^_n = T^_ + n\times\mathcal(1) = \mathcal(n)\).

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

    Метод математической индукции

    Позволяет доказать истинность некоторого утверждения (\(P_n\)), состоит из двух шагов:

    1. доказательство утверждения для одного или нескольких частных случаев \(P_0, P_1, …\);
    2. из истинности \(P_n\) (индуктивная гипотеза) и частных случаев выводится доказательство \(P_\).

    Докажем корректность предположения, сделанного при оценки трудоемкости функции поиска (\(T^_n = (n+1)\times\mathcal(1)\)):

    1. \(T^_ = 2\times\mathcal(1)\) верно из условия (можно подставить в исходную рекуррентную формулу);
    2. допустим истинность \(T^_n = (n+1)\times\mathcal(1)\);
    3. требуется доказать, что \(T^_ = ((n+1)+1)\times\mathcal(1) = (n+2)\times\mathcal(1)\);
      1. подставим \(n+1\) в рекуррентное соотношение: \(T^_ = \mathcal(1) + T^_n\);
      2. в правой части выражения возможно произвести замену на основании индуктивной гипотезы: \(T^_ = \mathcal(1) + (n+1)\times\mathcal(1) = (n+2)\times\mathcal(1)\);
      3. утверждение доказано.

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

      Общий (основной) метод решения рекуррентных соотношений

      \(T_n = a\cdot T(\frac)+f_n; a, b = const, a \geq 1, b > 1, f_n > 0, \forall n\).

      Уравнения такого вида получаются если исходная задача разделяется на a подзадач, каждая из которых обрабатывает \(\frac\) элементов. \(f_n\) — трудоемкость операций разбиения задачи на части и комбинирование решений. Помимо вида соотношения, общий метод накладывает ограничения на функцию \(f_n\), выделяя три случая:

      1. \(\exists \varepsilon > 0 : f_n = \mathcal(n^<\log_b a — \varepsilon>) \Rightarrow T_n = \Theta(n^<\log_b a>)\);
      2. \(f_n = \Theta(n^<\log_b a>) \Rightarrow T_n = \Theta(n^ <\log_b a>\cdot \log n)\);
      3. \(\exists \varepsilon > 0, c 1\).

      Для проведения анализа может использоваться метод подстановки или следующие рассуждения: каждый рекурсивный вызов уменьшает размерность входных данных на единицу, значит всего их будет n штук, каждый из которых имеет сложность \( \mathcal(1)\). Тогда \(T^_n = n \cdot \mathcal(1) = \mathcal(n)\).

      Анализ алгоритма сортировки слиянием

      Исходные данные разделяются на две части, обе из которых обрабатываются: \(a = 2, b = 2, n^ <\log_b a>= n\).

      При обработке списка, разделение может потребовать выполнения \(\Theta(n)\) операций, а для массива — выполняется за постоянное время (\(\Theta(1)\)). Однако, на соединение результатов в любом случае будет затрачено \(\Theta(n)\), поэтому \(f_n = n\).

      Используется второй случай теоремы: \(T^_n = \Theta(n^ <\log_b a>\cdot \log n) = \Theta(n \cdot \log n)\).

      Анализ трудоемкости быстрой сортировки

      В лучшем случае исходный массив разделяется на две части, каждая из которых содержит половину исходных данных. Разделение потребует выполнения n операций. Трудоемкость компоновки результата зависит от используемых структур данных — для массива \(\mathcal(n)\), для связного списка \(\mathcal(1)\). \(a = 2, b = 2, f_n = b\), значит сложность алгоритма будет такой же как у сортировки слиянием: \(T^_n = \mathcal(n \cdot \log n)\).

      Однако, в худшем случае в качестве опорного будет постоянно выбираться минимальный или максимальный элемент массива. Тогда \(b = 1\), а значит, мы опять не можем использовать основную теорему. Однако, мы знаем, что в этом случае будет выполнено n рекурсивных вызовов, каждый из которых выполняет разделение массива на части (\(\mathcal(n)\)) — значит сложность алгоритма \(T^_n = \mathcal(n^2)\).

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

      Хвостовая рекурсия и цикл

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

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

      Для реализации такого поведения используется стек (стек вызовов, call stack) — в него помещаются номер команды для возврата и информация о локальных переменных. Стек не является бесконечным, поэтому рекурсивные алгоритмы могут приводить к его переполнению, в любом случае на работу с ним может уходить значительная часть времени.

      В ряде случаев рекурсивную функцию достаточно легко заменить циклом, например, рассмотренные выше алгоритмы поиска и бинарного поиска [4]. В некоторых случаях требуется более творческий подход, но чаще всего такая замена оказывается возможной. Кроме того, существует особый вид рекурсии, когда рекурсивный вызов является последней операцией, выполняемой функцией. Очевидно, что в таком случае вызывающая функция не будет каким-либо образом изменять результат, а значит ей нет смысла возвращать управление. Такая рекурсия называется хвостовой — компиляторы автоматически заменяют ее циклом.

      Зачастую сделать рекурсию хвостовой помогает метод накапливающего параметра [7], который заключается в добавлении функции дополнительного аргумента-аккумулятора, в котором накапливается результат. Функция выполняет вычисления с аккумулятором до рекурсивного вызова. Хорошим примером использования такой техники служит функция вычисления факториала:
      \(fact_n = n \cdot fact(n-1) \\
      fact_3 = 3 \cdot fact_2 = 3 \cdot (2 \cdot fact_1) = 3\cdot (2 \cdot (1 \cdot fact_0)) = 6 \\
      fact_n = factTail_ \\
      \\
      factTail_ = factTail(n-1, accumulator \cdot n)\\
      factTail_ = factTail_ = factTail_ = factTail_ = 6
      \)

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

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

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



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

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

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

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



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

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

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

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

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

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

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




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


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




      То, что происходит в этой функции может и не быть абсолютно очевидным. Я поясню, что произойдет, когда вы вызовете функцию и передадите в нее цифру 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.

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

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




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




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

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

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

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

      Рекурсивные алгоритмы

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

      По-иному, рекурсия — это метод обобщённого представления объекта или воздействия через самого себя, с применением задаваемых раньше конкретных определений.

      Готовые работы на аналогичную тему

      Если число колец больше:

      1. Используя рекурсию переместите все кольца, за исключением одного, из источника в запас, применяя приёмник в качестве запаса.
      2. Переместите последнее кольцо из источника в приёмник.
      3. Переместите все кольца из запаса в приёмник, применяя источник в качестве запаса.

      Рекурсивные алгоритмы в программировании

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

      К примеру программная функция А обращается к функции В, а функция В обращается к функции А. Число вложенных обращений к функциям или процедурам следует называть глубиной рекурсии.

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

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

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

      Рекурсивные алгоритмы в других областях

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

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

      Цель лекции: изучить понятие, виды рекурсии и рекурсивную триаду, научиться разрабатывать рекурсивную триаду при решении задач на языке C++.

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

      Рекурсия – это определение объекта через обращение к самому себе.

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

      Прямое обращение функции к самой себе предполагает, что в теле функции содержится вызов этой же функции, но с другим набором фактических параметров . Такой способ организации работы называется прямой рекурсией. Например, чтобы найти сумму первых n натуральных чисел, надо сумму первых (n-1) чисел сложить с числом n , то есть имеет место зависимость: Sn=Sn-1+n . Вычисление происходит с помощью аналогичных рассуждений. Такая цепочка взаимных обращений в конечном итоге сведется к вычислению суммы одного первого элемента, которая равна самому элементу.

      При косвенном обращении функция содержит вызовы других функций из своего тела. При этом одна или несколько из вызываемых функций на определенном этапе обращаются к исходной функции с измененным набором входных параметров . Такая организация обращений называется косвенной рекурсией. Например, поиск максимального элемента в массиве размера n можно осуществлять как поиск максимума из двух чисел: одно их них – это последний элемент массива, а другое является максимальным элементом в массиве размера (n-1) . Для нахождения максимального элемента массива размера (n-1) применяются аналогичные рассуждения. В итоге решение сводится к поиску максимального из первых двух элементов массива.

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

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

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

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

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

      Анализ трудоемкости рекурсивных алгоритмов методом подсчета вершин дерева рекурсии

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

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

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

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

      Будем использовать следующие обозначения для конкретного входного параметра D :

      R(D) – общее число вершин дерева рекурсии,

      RV(D) – объем рекурсии без листьев ( внутренние вершины ),

      RL(D) – количество листьев дерева рекурсии,

      HR(D) – глубина рекурсии.

      Например, для вычисления n -го члена последовательности Фибоначчи разработана следующая рекурсивная функция :

      Тогда полное дерево рекурсии для вычисления пятого члена последовательности Фибоначчи будет иметь вид ( рис. 34.1):

      Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины.

      Пример 1. Задача о разрезании прямоугольника на квадраты.

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

      Разработаем рекурсивную триаду.

      Параметризация: m, n – натуральные числа , соответствующие размерам прямоугольника.

      База рекурсии: для m=n число получившихся квадратов равно 1, так как данный прямоугольник уже является квадратом.

      m \ne n

      Декомпозиция : если , то возможны два случая m или m > n . Отрежем от прямоугольника наибольший по площади квадрат с натуральными сторонами. Длина стороны такого квадрата равна наименьшей из сторон прямоугольника. После того, как квадрат будет отрезан, размеры прямоугольника станут следующие: большая сторона уменьшится на длину стороны квадрата, а меньшая не изменится. Число искомых квадратов будет вычисляться как число квадратов, на которые будет разрезан полученный прямоугольник , плюс один (отрезанный квадрат). К получившемуся прямоугольнику применим аналогичные рассуждения: проверим на соответствие базе или перейдем к декомпозиции ( рис. 34.2).

      Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины ( рис. 34.3).

      Реку́рсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.

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

      Определение в логике, использующее рекурсию, называется индуктивным (см., например, Натуральное число).

      Содержание

      Примеры

      Если число дисков равно одному, тогда:

      В противном случае:

      • Рекурсивно передвиньте все диски кроме одного из источника в запас, используя задание как запас
      • Передвиньте оставшийся диск из источника в задание
      • Передвиньте все диски из запаса в задание используя источник как запас

      Рекурсия в программировании

      Функции

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

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

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

      • См. также Примеры реализации функции факториал

      Данные

      Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):

      Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

      Рекурсия в физике

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

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

      Рекурсия в лингвистике

      Способность языка порождать вложенные предложения и конструкции. Базовое предложение кошка съела мышь может быть за счет рекурсии расширено как Ваня догадался, что кошка съела мышь, далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку (хотя в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Д. Эверетт). О рекурсии в лингвистике, ее разновидностях и наиболее характерных проявлениях в русском языке описано в статье Е.А.Лодатко "Рекурсивные лингвистические структуры" (см.: Рекурсивные лингвистические структуры)

      Цитаты

      Итерация от человека. Рекурсия — от Бога. — Л. Питер Дойч [1]

      Большая часть всех шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода. Известные высказывания: 'Чтобы понять рекурсию, нужно сначала понять рекурсию', 'Чтобы что-то сделать, надо что-то сделать', 'Для приготовления салата необходимы: огурцы, помидоры, салат'. Весьма популярна шутка о рекурсии, напоминающая словарную статью:

      Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:

      У попа была собака, он её любил,
      Она съела кусок мяса, он её убил,
      В землю закопал,
      Надпись написал:

      "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: …

      См. также

      Ссылки

      Wikimedia Foundation . 2010 .

      Полезное

      Смотреть что такое "Рекурсивный алгоритм" в других словарях:

      рекурсивный алгоритм — rekursyvusis algoritmas statusas T sritis automatika atitikmenys: angl. recursive algorithm vok. rekursiver Algorithmus, m rus. рекурсивный алгоритм, m pranc. algorithme récursif, m … Automatikos terminų žodynas

      рекурсивный алгоритм управления — rekursyvusis valdymo algoritmas statusas T sritis automatika atitikmenys: angl. recursive control algorithm vok. rekursiver Regelungs od. Steuerungs algorithmus, m rus. рекурсивный алгоритм управления, m pranc. algorithme de réglage récurrent, m … Automatikos terminų žodynas

      Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях… … Википедия

      Рекурсивный акроним — Рекурсивный акроним акроним (иногда бэкроним), который ссылается на себя. В среде компьютерных хакеров стало традиционным выбирать акронимы и аббревиатуры, которые косвенно или напрямую ссылаются на себя. Одним из самых ранних примеров… … Википедия

      Рекурсивный нисходящий парсер — (англ. Recursive descent parser) алгоритм синтаксического анализа, реализуемый путём взаимного вызова парсящих процедур, соответствующих правилам контекстно свободной грамматики или БНФ. Применения правил последовательно, слева направо … Википедия

      Алгоритм Казакова-Штаера — Рекурсивный способ создания режущей сетки с целью разбиения множества двумерных полигонов, содержащих острова, на безостровные участки. Может применяться в геоинформационных системах для преобразования островных полигонов в безостровные. Связать? … Википедия

      Алгоритм — У этого термина существуют и другие значения, см. Алгоритм (значения). Для улучшения этой статьи желательно?: Переработать оформление в соответствии с правил … Википедия

      Алгоритм поиска A* — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла Поиск… … Википедия

      Алгоритм сжатия PPM — У этого термина существуют и другие значения, см. Ppm. PPM (англ. Prediction by Partial Matching предсказание по частичному совпадению) адаптивный статистический алгоритм сжатия данных без потерь, основанный на контекстном… … Википедия

      Алгоритм де Кастельжо — В вычислительной математике алгоритм де Кастельжо, названный в честь его изобретателя Поля де Кастельжо рекурсивный метод определения формы многочленов Бернштейна или кривых Безье. Алгоритм де Кастельжо также может быть использован для разделения … Википедия

      Читайте также: