Содержание

Рекурсия — это… Что такое Рекурсия?

Рекурсивное изображение экрана Визуальная форма рекурсии страницы Википедии

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

Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.

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

В математике

В программировании

Функции

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

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

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

Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.

Любую рекурсивную функцию можно заменить циклом и стеком.

Данные

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

 struct element_of_list
 {
   element_of_list *next; /* ссылка на следующий элемент того же типа */
   int data; /* некие данные */
 };

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

В физике

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

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

В лингвистике

См. также: Рекурсия (лингвистика)

Способность языка порождать вложенные предложения и конструкции. Базовое предложение «кошка съела мышь» может быть за счёт рекурсии расширено как Ваня догадался, что кошка съела мышь, далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку. Однако, в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Дэниэл Эверетт (англ.)[1].

В культуре

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

«чтобы понять рекурсию, нужно сначала понять рекурсию».

Весьма популярна шутка о рекурсии, напоминающая словарную статью:

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

  • рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки»:

Нашёл следующие краткие сведения:
«СЕПУЛЬКИ — важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКАРИИ».

Я последовал этому совету и прочёл:
«СЕПУЛЬКАРИИ — устройства для сепуления (см.)».
Я поискал «Сепуление»; там значилось:
«СЕПУЛЕНИЕ — занятие ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКИ».

Лем С. «Звёздные дневники Ийона Тихого. Путешествие четырнадцатое.»

  • Рассказ из «Кибериады» о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).
  • Рекурсивные акронимы: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor) и т. д.

См. также

Примечания

dic.academic.ru

Слово РЕКУРСИВНЫЙ — Что такое РЕКУРСИВНЫЙ?

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

Слово рекурсивный английскими буквами(транслитом) — rekursivnyi

Значения слова рекурсивный. Что такое рекурсивный?

Рекурсивный

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

Начала современного естествознания. — 2006

Рекурсивный МНК

Также получающиеся в результате применения рекурсивного МНК (рекурсивные остатки) используются при тестировании стабильности параметров модели.

ru.wikipedia.org

Рекурсивный заем

Рекурсивный заем (1) Заем, при котором уполномочивающее лицо, или гарант, несет ответственность в случае, если должник не производит платежа. (2) Заем…

Финансово-инвестиционный словарь. — 2002

Рекурсивный язык

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

ru.wikipedia.org

Рекурсивный акроним

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

ru.wikipedia.org

РЕКУРСИВНЫЙ АКРОНИМ. Акроним (иногда бэкроним), который ссылается на себя. В среде компьютерных хакеров стало традиционным выбирать акронимы и аббревиатуры, которые косвенно или напрямую ссылаются на себя.

Бизнес-словарь

РЕКУРСИВНАЯ ТЕОРИЯ МНОЖЕСТВ

РЕКУРСИВНАЯ ТЕОРИЯ МНОЖЕСТВ — раздел тео-рии рекурсивных функций, в к-ром рассматриваются и классифицируются подмножества натуральных чисел с алгоритмич. точки зрения, а также исследуются структуры, возникающие в результате такой классификации.

Математическая энциклопедия. — 1977-1985

РЕКУРСИВНЫЕ ФУНКЦИИ И ПРЕДИКА́ТЫ

РЕКУРСИВНЫЕ ФУНКЦИИ И ПРЕДИКА́ТЫ — один из важнейших для оснований математики и математич. логики классов понятий, служащих уточнениями содержат. понятий эффективно вычислимой арифметической функции и эффективно разрешимого арифметического предиката…

Философская энциклопедия

Рекурсивная модель

Рекурсивная модель [recursive model] — динамическая модель, обладающая математическим свойством рекурсии. Это значит, что если даны, например, все переменные модели до момента (t-1)…

slovar-lopatnikov.ru

РЕКУРСИВНАЯ МОДЕЛЬ [recursive model] — динамическая модель, обладающая математическим свойством рекурсии. Это значит, что если даны, напр., все переменные модели до момента (t–1)…

Лопатников. — 2003

Рекурсивная функция (теория вычислимости)

Рекурсивные функции (от позднелатинского recursio — возвращение), название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметического алгоритма, т.е. такого алгоритма…

БСЭ. — 1969—1978

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

ru.wikipedia.org

РЕКУРСИВНАЯ ФУНКЦИЯ — ч а с т и ч н о р е к у р с и в н а я ф у н к ц и я,- одно из математич. уточнений интуитивного понятия вычислимой функции, определяемое следующим образом.

Математическая энциклопедия. — 1977-1985

Рекурсивное определение

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

ru.wikipedia.org

РЕКУРСИВНОЕ ОПРЕДЕЛЕНИЕ — часто применяемый в математике способ задания функций, при к-ром значение искомой функции в данной точке определяется через ее значения в предшествующих точках (при подходящем отношении предшествования).

Математическая энциклопедия. — 1977-1985

Русский язык

Рекурси́вный; кр. ф. -вен, -вна.

Орфографический словарь. — 2004

  1. рекуперация
  2. рекуррентный
  3. рекурсивные
  4. рекурсивный
  5. рекурсия
  6. релаксант
  7. релаксатор

wordhelp.ru

рекурсивный — это… Что такое рекурсивный?

  • рекурсивный — прил., кол во синонимов: 1 • общерекурсивный (1) Словарь синонимов ASIS. В.Н. Тришин. 2013 …   Словарь синонимов

  • рекурсивный — ая, ое. recursif adj., нем. rekursiv <лат. recursio мат. Такой, значение которого для данного аргумента исчисляется с помощью значений для предшествующих аргументов. ♦ Рекурсивная функция. Крысин 1998. Лекс. БСЭ 3: рекурси/вный …   Исторический словарь галлицизмов русского языка

  • рекурсивный — — [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации EN recursive …   Справочник технического переводчика

  • рекурсивный — рекурсивный, рекурсивная, рекурсивное, рекурсивные, рекурсивного, рекурсивной, рекурсивного, рекурсивных, рекурсивному, рекурсивной, рекурсивному, рекурсивным, рекурсивный, рекурсивную, рекурсивное, рекурсивные, рекурсивного, рекурсивную,… …   Формы слов

  • рекурсивный — См. ricorsivo …   Пятиязычный словарь лингвистических терминов

  • Рекурсивный — (от лат. recursio возвращение) возвращающий к прошлому, к предшествующему; рекурсивные функции функции, значения которых для данного аргумента вычисляются с помощью значений для предшествующих аргументов. В 1931 году австрийский математик и логик …   Начала современного естествознания

  • рекурсивный — рекурс ивный; кратк. форма вен, вна …   Русский орфографический словарь

  • рекурсивный — …   Орфографический словарь русского языка

  • рекурсивный — Syn: см. рекуррентный …   Тезаурус русской деловой лексики

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

  • dic.academic.ru

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

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

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

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

    Примеры

    • Метод Гаусса — Жордана для решения Системы линейных алгебраических уравнений является рекурсивным.
    • Факториал целого неотрицательного числа n обозначается n! и определяется как
      при n > 0 и n! = 1 при n = 0
    • Числа Фибоначчи определяются с помощью рекуррентного соотношения:
      Первое и второе числа Фибоначчи равны 1
      Для n > 2, ne число Фибоначчи равно сумме (n − 1)-го и (n − 2)-го чисел Фибоначчи
    • Практически все геометрические фракталы задаются в форме бесконечной рекурсии. (например, треугольник Серпинского).
    • Задача «Ханойские башни». Её содержательная постановка такова:
      В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.
      Рекурсивный вариант решения задачи можно описать так:

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

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

    • Передвиньте диск из источника в задание

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

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

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

    Функции

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

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

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

    Впрочем, имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивают выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. К сожалению, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Lisp), описание которого содержит все необходимые сведения.

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

    Данные

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

     class element_of_list
     {
       element_of_list *next; /* ссылка на следующий элемент того же типа */
       int data; /* некие данные */
     };
    

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

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

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

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

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

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

    Цитаты

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

    Юмор

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

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

    • Рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».
    • Рассказ о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).

    Русская народная сказка-песня «У попа была собака…» являет пример рекурсии:

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

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

    См. также

    Ссылки

    1. * Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
    • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

    Wikimedia Foundation. 2010.

    dic.academic.ru

    Рекурсия — Циклопедия

    Что такое рекурсия. самое простое объяснение // 3 минуты [2:15]

    Рекурсия (от лат. recurrere — «возвращаться») — самоповтор; метод определения понятия через само себя; включение некоторого объекта или события в самого себя как части. Явление связано с понятиями самоотсылка и самоподобие.

    Источник парадоксов и бесконечностей: при попытке «пройти» через некоторый рекурсивный объект, находишь в нём самого себя, снова проходишь него, и так по кругу: например, установив два зеркала лицами навстречу, глядя со стороны одного в сторону другого, видишь там отражение, попеременно, то другого зеркала, то этого в другом…

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

    Множество может включать различные атомарные элементы и/или другие множества. Элементы чистых множеств — это либо ничего (в случае ∅), либо другие чистые множества.

    Факториал целого неотрицательного числа n обозначается [math]n![/math] и определяется как [math]n!=n\times(n-1)![/math] при [math]0!=1[/math]

    Рекуррентные последовательности — это те, в которых значение некоторого (n-го) элемента получается через преобразование других (более базовых). Классический пример — последовательность Фибоначчи: первые два элемента равны 1, каждый последующий — сумма двух предыдущих.

    Золотое сечение φ = 1 + 1/φ и, например, [math]\varphi = \sqrt{1 + \sqrt{1 + \sqrt{1 + \sqrt{1 + \cdots}}}}.[/math]

    Алгоритм Жордана-Гаусса для решения систем линейных алгебраических уравнений является рекурсивным.

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

    Лекция 4: Рекурсия // НОУ ИНТУИТ [1:45:05]
    • рекурсивная формула;
    • рекурсивная функция;
    • рекурсивная последовательность;
    • рекурсивный алгоритм;
    • рекурсивная программа;
    • рекурсивное изображение.

    [править] Рекурсия в программировании

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

    [править] Функции

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

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

    [править] Хвостовая рекурсия

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

    Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), выполняют хвостовую рекурсию в ограниченном объёме памяти при помощи итераций: «зацикленность» программной структуры выслеживается на стадии компиляции, и при работе программы не потребуются ресурсы для выделения памяти отдельно для каждого уровня рекурсивной вложенности.

    [править] Данные

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

    class element_of_list; /* необходимо по правилам C++ */
    class element_of_list
    {
      element_of_list *next; /* ссылка на следующий элемент того же типа */
      int data; /* некие данные */
    };
    

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

    В гуманитарных областях особые рекурсивные явления называются эффект Дросте и Mise en abyme (мизинаби́м.)

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

    • Рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».
    • Рассказ о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).

    [править] Юмор

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

    Распространено остроумное «энциклопедическое определение» рекурсии через самодемонстрацию: «Рекурсия: см. рекурсия

    [править] Другие алгоритмы

    • Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4.
    • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.

    cyclowiki.org

    рекурсивный — Викисловарь

    Содержание

    • 1 Русский
      • 1.1 Морфологические и синтаксические свойства
      • 1.2 Произношение
      • 1.3 Семантические свойства
        • 1.3.1 Значение
        • 1.3.2 Синонимы
        • 1.3.3 Антонимы
        • 1.3.4 Гиперонимы
        • 1.3.5 Гипонимы
      • 1.4 Родственные слова
      • 1.5 Этимология
      • 1.6 Фразеологизмы и устойчивые сочетания
      • 1.7 Перевод
      • 1.8 Библиография

    Морфологические и синтаксические свойства[править]

    падеж ед. ч. мн. ч.
    муж. р. ср. р. жен. р.
    Им.рекурси́вныйрекурси́вноерекурси́внаярекурси́вные
    Рд.рекурси́вногорекурси́вногорекурси́внойрекурси́вных
    Дт.рекурси́вномурекурси́вномурекурси́внойрекурси́вным
    Вн.   одуш.рекурси́вногорекурси́вноерекурси́внуюрекурси́вных
    неод.рекурси́вныйрекурси́вные
    Тв.рекурси́внымрекурси́внымрекурси́вной рекурси́вноюрекурси́вными
    Пр.рекурси́вномрекурси́вномрекурси́внойрекурси́вных
    Кратк. формарекурси́венрекурси́внорекурси́внарекурси́вны

    ре-кур-си́в-ный

    Прилагательное, тип склонения по классификации А. Зализняка — 1*a.

    Корень: .

    Произношение[править]

    • МФА: [rʲɪkʊrˈsʲivnɨɪ̯]

    Семантические свойства[править]

    Значение[править]
    1. матем. обращающийся в своём определении к самому себе (о функции, подпрограмме) ◆ Отсутствует пример употребления (см. рекомендации).
    Синонимы[править]
    1. рекуррентный
    Антонимы[править]
    Гиперонимы[править]
    1. вычисляемый
    Гипонимы[править]

    Родственные слова[править]

    Ближайшее родство
    • существительные: рекурсия, рекурсивность
    • наречия: рекурсивно

    Этимология[править]

    Происходит от ??

    Фразеологизмы и устойчивые сочетания[править]

    Перевод[править]

    Список переводов
    • Английскийen: fractal, recursive

    Библиография[править]

    Для улучшения этой статьи желательно:
    • Добавить описание морфемного состава с помощью {{морфо-ru}}
    • Добавить пример словоупотребления для значения с помощью {{пример}}
    • Добавить сведения об этимологии в секцию «Этимология»

    ru.wiktionary.org

    Рекурсивная функция — Википедия

    Материал из Википедии — свободной энциклопедии

    Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция f(n){\displaystyle f(n)} числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения f(n){\displaystyle f(n)} на основе значений f(n−1),f(n−2),…{\displaystyle f(n-1),f(n-2),\ldots }, подобно рассуждению по индукции. Чтобы вычисление завершалось для любого n{\displaystyle n}, необходимо, чтобы для некоторых n{\displaystyle n} функция была определена нерекурсивно (например, для n=0,1{\displaystyle n=0,1}).

    Пример рекурсивной функции, дающей n-ое число Фибоначчи:

    F={F(0)=1;F(1)=1;F(n)=F(n−1)+F(n−2),n>1.{\displaystyle F={\begin{cases}F(0)=1;\\F(1)=1;\\F(n)=F(n-1)+F(n-2),\quad n>1.\end{cases}}}

    Руководствуясь этой записью, мы можем вычислить F(n){\displaystyle F(n)} для любого натурального n за конечное число шагов. Правда, по пути придётся дополнительно вычислить значения F(n−1),F(n−2),…,F(2){\displaystyle F(n-1),F(n-2),\ldots ,F(2)}.

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

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

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

    f={f(0)=0;f(n)=n+f(n−1),n>0{\displaystyle f={\begin{cases}f(0)=0;\\f(n)=n+f(n-1),\quad n>0\end{cases}}}

    может быть переведена в замкнутую форму: f=n(n+1)2{\displaystyle f={\frac {n(n+1)}{2}}}.

    Рекурсивные функции играют важную роль в теории алгоритмов, так как многие алгоритмы имеют рекурсивную структуру.

    ru.wikipedia.org