На сколько неокортекс отвечает за перспективные цели. Структуры лимбической системы и неокортекса
Рекурсивный алгоритм
Реку́рсия - метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.
Другими словами, рекурсия - способ общего определения объекта или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно выделить самоподобие задачи.
Примеры
Алгоритм по передвижению башни, алгоритм передвинет нужное количество дисков из пирамиды «источник» на пирамиду «задание» используя «запасную» пирамиду.
Если число дисков равно одному, тогда:
- Передвиньте диск из источника в задание
В противном случае:
- Рекурсивно передвиньте все диски кроме одного из источника в запас, используя задание как запас
- Передвиньте оставшийся диск из источника в задание
- Передвиньте все диски из запаса в задание используя источник как запас
Рекурсия в программировании
Функции
Class element_of_list { element_of_list *next; /* ссылка на следующий элемент того же типа */ int data; /* некие данные */ } ;
Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.
Рекурсия в физике
Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала : в них образуются два коридора из затухающих отражений зеркал.
Другим примером бесконечной рекурсии является эффект самовозбуждения (положительной обратной связи) у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы .
Рекурсия в лингвистике
Способность языка порождать вложенные предложения и конструкции. Базовое предложение кошка съела мышь может быть за счет рекурсии расширено как Ваня догадался, что кошка съела мышь , далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий , то есть свойственна любому естественному языку (хотя в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии - пираха, которое отмечает лингвист Д. Эверетт). О рекурсии в лингвистике, ее разновидностях и наиболее характерных проявлениях в русском языке описано в статье Е.А.Лодатко "Рекурсивные лингвистические структуры" (см.: Рекурсивные лингвистические структуры)
Цитаты
Юмор
Большая часть всех шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода. Известные высказывания: "Чтобы понять рекурсию, нужно сначала понять рекурсию", "Чтобы что-то сделать, надо что-то сделать", "Для приготовления салата необходимы: огурцы, помидоры, салат". Весьма популярна шутка о рекурсии, напоминающая словарную статью:
Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:
- Рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого », в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».
- Рассказ о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).
Русская народная сказка-песня «У попа была собака…» являет пример рекурсии:
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:"У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: …
См. также
- Рекуррентная последовательность (возвратная последовательность)
Ссылки
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: «Вильямс» , 2006. - С. 1296. - ISBN 0-07-013151-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* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла Поиск… … Википедия
У этого термина существуют и другие значения, см. Ppm. PPM (англ. Prediction by Partial Matching предсказание по частичному совпадению) адаптивный статистический алгоритм сжатия данных без потерь, основанный на контекстном… … Википедия
Здравствуй Хабрахабр!
В этой статье речь пойдет о задачах на рекурсию и о том как их решать.
Кратко о рекурсии
Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).
О рекурсии сказано много. Вот несколько хороших ресурсов:
- Рекурсия и рекурсивные задачи. Области применение рекурсии
Задачи
При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач.Как же решать задачи на рекурсию?
В первую очередь надо понимать что рекурсия это своего рода перебор. Вообще говоря, всё то, что решается итеративно можно решить рекурсивно, то есть с использованием рекурсивной функции.из сети
Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде и наоборот. Останется вопрос, надо ли это, и насколько это будет это эффективно.
Для обоснования можно привести такие доводы.
Для начала можно вспомнить определение рекурсии и итерации. Рекурсия - это такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ. Итерация - это способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.
После чего можно сделать вывод, что они взаимно заменимы, но не всегда с одинаковыми затратами по ресурсам и скорости. Для обоснования можно привести такой пример: имеется функция, в которой для организации некого алгоритма имеется цикл, выполняющий последовательность действий в зависимости от текущего значения счетчика (может от него и не зависеть). Раз имеется цикл, значит, в теле повторяется последовательность действий - итерации цикла. Можно вынести операции в отдельную подпрограмму и передавать ей значение счетчика, если таковое есть. По завершению выполнения подпрограммы мы проверяем условия выполнения цикла, и если оно верно, переходим к новому вызову подпрограммы, если ложно - завершаем выполнение. Т.к. все содержание цикла мы поместили в подпрограмму, значит, условие на выполнение цикла помещено также в подпрограмму, и получить его можно через возвращающее значение функции, параметры передающееся по ссылке или указателю в подпрограмму, а также глобальные переменные. Далее легко показать, что вызов данной подпрограммы из цикла легко переделать на вызов, или не вызов (возврата значения или просто завершения работы) подпрограммы из нее самой, руководствуясь какими-либо условиями (теми, что раньше были в условии цикла). Теперь, если посмотреть на нашу абстрактную программу, она примерно выглядит как передача значений подпрограмме и их использование, которые изменит подпрограмма по завершению, т.е. мы заменили итеративный цикл на рекурсивный вызов подпрограммы для решения данного алгоритма.
Задача по приведению рекурсии к итеративному подходу симметрична.
Подводя итог, можно выразить такие мысли: для каждого подхода существует свой класс задач, который определяется по конкретным требованиям к конкретной задаче.
Более подробно с этим можно познакомиться
Так же как и у перебора (цикла) у рекурсии должно быть условие остановки - Базовый случай (иначе также как и цикл рекурсия будет работать вечно - infinite). Это условие и является тем случаем к которому рекурсия идет (шаг рекурсии). При каждом шаге вызывается рекурсивная функция до тех пор пока при следующем вызове не сработает базовое условие и произойдет остановка рекурсии(а точнее возврат к последнему вызову функции). Всё решение сводится к решению базового случая. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.
Итак рекурсивная функция состоит из
- Условие остановки или же Базовый случай
- Условие продолжения или Шаг рекурсии - способ сведения задачи к более простым.
Public class Solution { public static int recursion(int n) { // условие выхода // Базовый случай // когда остановиться повторять рекурсию? if (n == 1) { return 1; } // Шаг рекурсии / рекурсивное условие return recursion(n - 1) * n; } public static void main(String args) { System.out.println(recursion(5)); // вызов рекурсивной функции } }
Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.
Теги:
- рекурсия
- задачи
- java
