Рекурсия

Слово рекурсия

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

Слово рекурсия состоит из 8 букв: е и к р р с у я


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

Рекурсия

Реку́рсия — наличие в определении, описании, изображении какого-либо объекта или процесса самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.

ru.wikipedia.org

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

Энциклопедический фонд России

РЕКУРСИЯ — способ определения функций, являющийся объектом изучения в теории алгоритмов и других разделах математич. логики. Этот способ давно применяется в арифметике для определения числовых последовательностей (прогрессии, чисел Фибоначчи и пр.).

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

Рекурсия (фонетика)

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

ru.wikipedia.org

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

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

ru.wikipedia.org

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

ПРИМИТИВНАЯ РЕКУРСИЯ — способ определения функций от натуральных аргументов с натуральными значениями. Говорят, что (n+1)-местная функция f(x 1, …, х п, у). получена примитивной рекурсией из n-местной функции g…

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

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

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

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

РЕКУРСИИ ВЫСШИХ СТУПЕНЕЙ

РЕКУРСИИ ВЫСШИХ СТУПЕНЕЙ — рекурсивные определения, в к-рых в качестве вспомогательных объектов наряду с числовыми функциями используются нек-рые функционалы более высоких типов.

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

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

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

ru.wikipedia.org

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

такого алгоритма…Оператор примитивной рекурсии сопоставляет функциям f от n переменных и g от n + 2 переменных функцию h от n + 1 переменных такую, что для любых натуральных чисел x1,…., xn, y h(x1…

БСЭ. — 1969—1978

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

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


.

Раздел: Курсы / Указатели /

Рекурсия

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

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

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

Примером рекуррентной последовательности являются, например, арифметическая прогрессия и геометрическая прогрессия.

То есть в рекуррентной последовательности содержится какое-то количество чисел (в общем случае – бесконечное). Каждое число в такой последовательности вычисляется через предыдущее число (или через ряд предыдущих чисел).

Например, есть такая арифметическая прогрессия:

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

ai = ai-1 + 3

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

Для примера рассмотрим классический случай рекуррентной последовательности – числа Фибоначчи:

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

Формула для определения чисел Фибоначчи выглядит так:

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

Каждое число в последовательности имеет порядковый номер (индекс) от 1 до бесконечности. Этот порядковый номер обозначается буквой i. Если i равно 1 или 2, то число в последовательности будет равно 1 (a1 = 1, a2 = 1). Если i > 2, то число вычисляется по формуле:

ai = fi-1 + fi-2

Здесь буквой f обозначена функция, по которой выполняется вычисление. В нашем случае функция проста – она просто получает число с указанным индексом.

А теперь разберёмся с тем, как реализовать рекурсию в программировании, а конкретно на языке Паскаль.

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

Пример использования рекурсивного вызова функции для вычисления чисел Фибоначчи приведён в листинге 3.3.

Листинг 3.3. Рекурсивное вычисление чисел Фибоначчи. program ukaz; {$mode objfpc}{$H+} //********************************************************************** // Вычисляет число Фибоначчи //********************************************************************** function Fibonachi(Num : integer) : integer; begin if (Num = 1) or (Num = 2) then //Если это 1-й или 2-й элемент Result := 1 else //Иначе функция вызывает сама себя (рекурсия) Result := Fibonachi(Num-1) + Fibonachi(Num-2); end; var i : integer; //********************************************************************** // ОСНОВНАЯ ПРОГРАММА //********************************************************************** begin for i := 1 to 10 do Write(Fibonachi(i), ‘ ‘); ReadLn; end.

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

Усилители, для которых такой режим работы является штатным, называются автогенераторы.

Цитаты

Итерация от человека. Рекурсия — от Бога.

— Л. Питер Дойч (Д. Кнут. Искусство программирования.)

Юмор

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

рекурсия 
см. рекурсия

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

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

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

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

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

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

(кавычки цитат никогда не закроются)

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

Алгоритм обхода дерева в прямом порядке (рекурсивный)

  • посетить корень
  • посетить каждое поддерево в прямом порядке

    Необходимые данные:

  • массив son — список узлов и сыновей для них
  • числовые массивы left и right
    void Obhod_Dereva_Prymoi_Poryadok (int node)// функция получает в качестве аргумента номер узла{printf("%d\n", son[node]); // где массив son хранит "сыновей"   if(left[node]!=0) Obhod_Dereva_Prymoi_Poryadok (left[node]); if(right[node]!=0) Obhod_Dereva_Prymoi_Poryadok (right[node]);   return; }

    Алгоритм обхода дерева в обратном порядке (рекурсивный)

  • посетить каждое поддерево в обратном порядке
  • посетить корень

    Необходимые данные:

  • массив son — список узлов и сыновей для них
  • числовые массивы left и right
    void Obhod_Dereva_Obratniy_Poryadok (int node)// функция получает в качестве аргумента номер узла{if(left[node]!=0) Obhod_Dereva_Obratniy_Poryadok (left[node]); if(right[node]!=0) Obhod_Dereva_Obratniy_Poryadok (right[node]);   printf("%d\n", son[node]); // где массив son хранит "сыновей"   return; }

    Алгоритм обхода дерева во внутреннем порядке (рекурсивный)

    Необходимые данные:

  • массив son — список узлов и сыновей для них
  • числовые массивы left и right
    void Obhod_Dereva_Vnutr_Poryadok (int node)// функция получает в качестве аргумента номер узла{if(left[node]!=0) Obhod_Dereva_Vnutr_Poryadok (left[node]);   printf("%d\n", son[node]); // где массив son хранит "сыновей"   if(right[node]!=0) Obhod_Dereva_Vnutr_Poryadok (right[node]);   return; }
  • Ключевые слова: 

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

    Добавить комментарий

    Закрыть меню