Что такое рекурсия в математике

Что такое рекурсия в математике

Петя. Математики любят рекурсию и пользуются ею при записи математических формул. Формулы получаются очень компактными. Хочу продемонстрировать тебе эту математическую привязанность на двух примерах.

Факториал

Например, 3! = 1·2·3 = 6.

Формулу для факториала можно записать так:

Это обычная, не рекурсивная формула. Читаем так: эн факториал есть произведение всех натуральных чисел от 1 до n ( включая n).

Заметим, что произведение всех натуральных чисел от 1 до n, исключая n есть факториал числа на единицу меньшего n, то есть факториал числа (n-1). Получаем:

Отсюда получается формула, содержащая рекурсию:

Читается формула так: факториал числа n есть 1, если n=1, иначе (при n>1) он равен факториалу от числа (n-1) умноженному на n.

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

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

Сводим
вычисление 4! к вычислению 3!,
вычисление 3! к вычислению 2!,
вычисление 2! к вычислению 1!,
а 1! вычисляем непосредственно, он равен 1.

Рекурсивное погружение выполняется до тех пор, пока не выполнится проверка на окончание рекурсии (в нашем случае n=1 ), затем начинается всплытие, которое продолжается, пока управление не получит первая процедура, стартовавшая рекурсию.

Последовательность Фибоначчи

О последовательности Фибоначчи уже упоминалось в третьей части курса, когда шёл разговор о золотом сечении. Вы не забыли что это такое?

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

В той же пропорции находятся:

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

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

Последовательность Фибоначчи названа так в честь учёного, который её открыл. Интересно, что Фибоначчи — это не имя, а прозвище, а настоящие имя — Леонардо Пизанский — крупный математик средневековой Европы, родился около 1170 года в итальянском городе Пиза (этот город, кстати, знаменит ещё и «падающей» пизанской башней, посмотрите в Интернете).

F 1 =1
F 2 =1
F n = F n-1 + F n-2 (для всех n>2)

По этим формулам можно написать рекурсивную программу с переключателем:

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

Рекурсивное погружение выполняется до тех пор, пока не выполнится проверка на окончание рекурсии ( n=1 или n=2 ), затем начинается всплытие, которое продолжается, пока управление не получит первая процедура, стартовавшая рекурсию.

Рекурсивный Кукарача

Вернёмся от математики на поле Кукарачи и попробуем решить такую задачу.

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

Вася. Надо столкнуть кубики, затем спустится вниз. В главной процедуре получается 2 команды, первая описывается процедурой с циклом ПОКА (количество кубиков неизвестно), а вторая — процедурой с циклом ПОВТОРИ :

Почему ты пометил последнюю процедуру знаком вопроса?

Петя. Она будет правильно работать только в одном случае: когда исходно на поле стояло 4 кубика!

Вася. Получается так… Но я не знаю, как заставить Кукарачу сосчитать кубики!

На этапе всплытия Кукарача выполняются возвраты и выполнение всех отложенных команд ВНИЗ :

Вася. Получилось замечательно! Так как количество отложенных команд ВНИЗ равно числу кубиков, Кукарача точно выполнит условие задачи.

Петя. Процедуру Спуск можно записать короче:

Рекурсивное погружение заканчивается, когда исполнитель шагает в пустую клетку. Условие в команде ЕСЛИ становится ложным, выполнение процедуры завершается, и начинается рекурсивное всплытие:

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

Петя. В этом варианте команд ВНИЗ выполнится на одну больше, чем нужно. Посмотри:

Вася. Да, верно. Один раз команда ВНИЗ сработает на этапе погружения, когда исполнитель переходит в пустую клетку ( Спуск уже не вызывается).

Получается, Кукарача шагнёт вниз даже тогда, когда на поле изначально нет кубиков.

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

Вася. Думаю, задача решается таким рекурсивным кодом:

Источник

Рекурсия. Занимательные задачки

В этой статье речь пойдет о задачах на рекурсию и о том как их решать.

Кратко о рекурсии

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.

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

Задачи

При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач.

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

Для обоснования можно привести такие доводы.

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

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

Задача по приведению рекурсии к итеративному подходу симметрична.

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

Более подробно с этим можно познакомиться тут

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

Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.

В сети при обьяснении рекурсии также даются задачи нахождения чисел Фибоначчи и Ханойская башня

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

Поехали! Решения задач предоставлены на языке Java.

A: От 1 до n
Дано натуральное число n. Выведите все числа от 1 до n.

Источник

Что такое рекурсия в математике

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

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

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

Для рекурсии в её наиболее общей, неитеративной форме типична необходимость отсрочки некоторых действий; см., в частности, пример (4). По этой причине она вряд ли показана для забывчивых людей, но вполне пригодна для подходящим образом оборудованных машин. Повторение же — это в значительной степени наш повседневный опыт. см. 3, 4, 6. Бауэр Гооз

3.2. Примеры

Пример 1. Вспомним определение натуральных чисел. Оно состоит из двух частей:

1. 1 — натуральное число;

2. если n — натуральное число, то n + 1 — тоже натуральное число.

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

Первая часть в определении натуральных чисел — это и есть тот самый базовый случай. Если убрать первую часть из определения, оно будет неполно: вторая часть даёт только метод перехода к следующему значению, но не даёт никакой «зацепки», не отвечает на вопрос «откуда начать».

Пример 3. Популярные примеры рекурсивных объектов — фракталы. Так в математике называют геометрические фигуры, обладающие самоподобием. Это значит, что они составлены из фигур меньшего размера, каждая из которых подобна целой фигуре. На рисунке 8.2 показан треугольник Серпинского — один из первых фракталов, который предложил в 1915 г. польский математик В. Серпинский. Рис. 8.2

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

Пример 4. Ханойские башни.

Согласно легенде, конец света наступит тогда, когда монахи Великого храма города Бенарас смогут переложить 64 диска разного диаметра с одного стержня на другой. Вначале все диски нанизаны на первый стержень. За один раз можно перекладывать только один диск, причём разрешается класть только меньший диск на больший. Есть также и третий стержень, который можно использовать в качестве вспомогательного (рис. 8.3).

Решить задачу для 2, 3 и даже 4 дисков довольно просто. Проблема в том, чтобы составить алгоритм для любого числа дисков.

Пусть нужно перенести n дисков со стержня 1 на стержень 3. Представим себе, что мы как-то смогли переместить n – 1 дисков на вспомогательный стержень 2. Тогда остается перенести самый большой диск на стержень 3, а затем n — 1 меньших дисков со вспомогательного стержня 2 на стержень 3, и задача будет решена. Получается такой псевдокод:

Процедура перенести (которую нам предстоит написать) принимает три параметра: число дисков, начальный и конечный стержни. Таким образом, мы свели задачу переноса n дисков к двум задача переноса n – 1 дисков и одному элементарному действию — переносу 1 диска. Заметим, что при известных номерах начального и конечного стержней легко рассчитать номер вспомогательного, так как сумма номеров равна 1 + 2 + 3 = 6. Получается такая (пока не совсем верная) процедура:

алг Hanoi (цел п, к, m )

Эта процедура вызывает сама себя, но с другими значениями параметров. Такая процедура называется рекурсивной.

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

Основная программа для решения задачи, например, с четырьмя дисками будет содержать всего одну строку (перенести 4 диска со стержня 1 на стержень 3):

Если вы попробуете запустить эту программу, она зациклится, т. е. будет работать бесконечно долго. В чём же дело? Вспомните, что определение рекурсивного объекта состоит из двух частей. В первой части определяются базовые объекты (например, первое натуральное число), именно эта часть «отвечает» за остановку рекурсии в программе. Пока мы не определили такое условие останова, процедура будет бесконечно вызывать саму себя (это можно проверить, выполняя программу по шагам). Когда же остановить рекурсию?

Очевидно, что если нужно переложить 0 дисков, задача уже решена, ничего перекладывать не надо. Это и есть условие окончания рекурсии: если значение параметра п, переданное процедуре, равно 0, нужно выйти из процедуры без каких-либо действий. Для этого в школьном алгоритмическом языке используется оператор выход (в Паскале — оператор exit ). Правильная версия процедуры выглядит так:

procedure Hanoi (n,k,m:integer);

Чтобы переложить N дисков, нужно выполнить 2 N — 1 перекладываний. Для N = 64 это число равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, каждую секунду перемещали один диск, им бы потребовалось 580 миллиардов лет.

Пример 5. Составим процедуру, которая переводит натуральное число в двоичную систему. Мы уже занимались вариантом этой задачи, где требовалось вывести 8-битную запись числа из диапазона 0..255, сохранив лидирующие нули. Теперь усложним задачу: лидирующие нули выводить не нужно, а натуральное число может быть любым (в пределах допустимого диапазона для выбранного типа данных).

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

Проблема в том, что двоичное число выводится «задом наперёд», т. е. первым будет выведен последний разряд. Как «перевернуть» число?

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

Такой алгоритм очень просто программируется:

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

алг цел sumDig( цел n)

sum:=sum+sumDig (n div 10);

Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел.

алг цел NOD( цел a, b)

если а=0 или b =0 то

иначе знач :=N0D(a, b-a)

function NOD(a, b:integer):integer

if (a=0) or (b=0) then begin

Существует и более быстрый вариант алгоритма Евклида (модифицированный алгоритм), в котором большее число заменяется на остаток от деления большего числа на меньшее.

Рассмотрим ещё несколько алгоритмов, которые можно реализовать с помощью рекурсии:

1. Алгоритм сложения двух положительных десятичных чисел.

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

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

2. Алгоритмы разложения натурального числа на простые множители.

Если же таблицы простых чисел в распоряжении нет, то можно также последовательно пытаться делить заданное число на натуральные числа 2, 3, 4, 5, 6, 7. до тех пор, пока не останется 1; при этом для каждого составного числа как делителя выполняемая попытка деления будет бесполезной.

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

В данном случае количество элементарных тактов обработки зависит от величины разлагаемого числа.

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

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

В данном случае количество элементарных тактов обработки зависит от размера картотеки

4. Алгоритм сортировки (несортированной) картотеки.

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

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

Этот пример демонстрирует иерархическую структуру: алгоритм сортировки основан на алгоритме смешивания.

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

5. Алгоритм вычисления значения дроби (а + b )/(а — b ).

Сначала вычисляем (используя алгоритмы сложения и вычитания) значения выражений а + b и а — b (все равно, последовательно или одновременно, поскольку ситуация здесь совместная), а потом образуем частное от деления полученных результатов (используя алгоритм деления).

В случае общих формул обнаруживается как иерархическое строение, так и совместность.

В данном случае количество элементарных тактов обработки бесконечно.

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

7. Алгоритм вычисления числа е (т. е. вычисления последовательности дробей — приближений для е).

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

Источник

Рекурсия. Беглый взгляд

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

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

Определение

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

Самая большая глупость — это делать то же самое и надеяться на другой результат.

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

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

Некоторые примеры

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

Отличный пример вы можете найти тут.

Самое известное программисту применение рекурсии — задачи на вычисление чисел Фибоначчи или факториала. Давайте покажем, как это реализовать на языке C:

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

Fork-бомба
Примечание: Рекурсивное создание процессов крайне быстро (из-за экспоненциального роста их количества) заполняет таблицу процессов, что достаточно опасно для системы.

Reboot кнопкой после такого делать немного не приятно.

Для математика первой ассоциацией, скорее всего, будет фрактал. Фракталы прекрасны и приятно для глаза показывают свойства самоподобия.

Самые известные фракталы:

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

Углубимся глубже

Проста ли рекурсия? Однозначно нет. На вид кажется, что всё просто, однако рекурсия таит в себе опасности (А иногда она просто не понятна).

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

Заметим, что дерево вызовов получится большим, но максимальное количество вызовов в стеке будет заметно меньше (N-1 при N > 2, соответственно).

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

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

Для полноты картины обязательно надо упомянуть о борьбе с рекурсией.

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

Под силу ли побороть любую рекурсию?

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

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

Заключение

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

UPD: Добавлен корректный пример хвостовой рекурсии.

Источник