Рекурсивный способ задания функции это
а) Терминологическое введение
По сути один и тот же метод, применительно к различным областям носит различные названия – это индукция, рекурсия и рекуррентные соотношения – различия касаются особенностей использования.
Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при n=0,1, затем утверждение полагается правильным при n=n b и проводится доказательство для n+1.
Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.
Термин рекуррентные соотношения связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.
Основной задачей исследования рекурсивно заданных функций является получение f(n) в явной или как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции. В связи с этим рассмотрим ряд примеров:
б) Примеры рекурсивного задания функций
| 1. | f(0)=0 f(n)= f(n-1)+1 |
| 2. | f(0)=1 f(n)= n*f(n-1) |
Последовательная подстановка дает – f(n)=1*2*3*…*n = n!
Для полноты сведений приведем формулу Стирлинга для приближенного вычисления факториала для больших n:
| 3. | f(0)=1 f(1)=1 f(n)= f(n-1)+ f(n-2), n>=2 |
Эта рекурсивная функция определяет числа Фибоначчи: 1 1 2 3 5 8 13, которые достаточно часто возникают при анализе различных задач, в том числе и при анализе алгоритмов. Отметим, что асимптотически
| 4. | f(0)=1 f(n)= f(n-1)+ f(n-2)+…+1 = f(i)+1 |
Для получения функции в явном виде рассмотрим ее последовательные значения: f(0)=1, f(1)=2, f(2)=4, f(3)=8, что позволяет предположить, что f(n)= , точное доказательство выполняется по индукции.
| 5. | f(0)=1 f(n)= 2*f(n-1) |
Мы имеем дело с примером того, что одна и та же функция может иметь различные рекурсивные определения – f(n)= , как и в примере 4, что проверяется элементарной подстановкой.
| 6. | f(0)=1 f(1)=2 f(n)= f(n-1)*f(n-2) |
В этом случае мы можем получить решение в замкнутой форме, сопоставив значениям функции соответствующие степени двойки:
Обозначив через Fn — n-ое число Фибоначчи, имеем: f(n)= .
Рекурсивная реализация алгоритмов
Большинство современных языков высокого уровня поддерживают механизм рекурсивного вызова, когда функция, как элемент структуры языка программирования, возвращающая вычисленное значение по своему имени, может вызывать сама себя с другим аргументом. Эта возможность позволяет напрямую реализовывать вычисление рекурсивно определенных функций. Отметим, что в силу тезиса Черча–Тьюринга аппарат рекурсивных функций Черча равномощен машине Тьюринга, и, следовательно, любой рекурсивный алгоритм может быть реализован итерационно.
F(n);
If n=0 or n=1 (проверка возможности прямого вычисления)
Then
F
Рис 8.1 Дерево рекурсии при вычислении факториала – F(5)
Дерево рекурсивных вызовов может иметь и более сложную структуру, если на каждом вызове порождается несколько обращений – фрагмент дерева рекурсий для чисел Фибоначчи представлен на рис 8.2:
Рис 8.2 Фрагмент дерева рекурсии при вычислении чисел Фибоначчи – F(5)
Анализ трудоемкости механизма вызова процедуры
Механизм вызова функции или процедуры в языке высокого уровня существенно зависит от архитектуры компьютера и операционной системы. В рамках IBM PC совместимых компьютеров этот механизм реализован через программный стек. Как передаваемые в процедуру или функцию фактические параметры, так и возвращаемые из них значения помещаются в программный стек специальными командами процессора. Дополнительно сохраняются зна-чения необходимых регистров и адрес возврата в вызывающую процедуру. Схематично этот механизм иллюстрирован на рис 8.3:
Рис 8.2 Механизм вызова процедуры с использованием программного стека
Для подсчета трудоемкости вызова будем считать операции помещения слова в стек и выталкивания из стека элементарными операциями в формальной системе. Тогда при вызове процедуры или функции в стек помещается адрес возврата, состояние необходимых регистров процессора, адреса возвращаемых значений и передаваемые параметры. После этого выполняется переход по адресу на вызываемую процедуру, которая извлекает переданные фактические параметры, выполняет вычисления, помещает их по указанным в стеке адресам, и при завершении работы восстанавливает регистры, выталкивает из стека адрес возврата и осуществляет переход по этому адресу.
Обозначив через:
m — количество передаваемых фактических параметров,
k — количество возвращаемых процедурой значений,
r — количество сохраняемых в стеке регистров,
имеем:
fвызова = m+k+r+1+m+k+r+1 = 2*(m+k+r+1) элементарных операций на один вызов и возврат.
Анализ трудоемкости рекурсивных алгоритмов в части трудоемкости самого рекурсивного вызова можно выполнять разными способами в зависимости от того, как формируется итоговая сумма элементарных операций – рассмотрением в отдельности цепочки рекурсивных вызовов и возвратов, или совокупно по вершинам дерева рекурсивных вызовов.
Анализ трудоемкости алгоритма вычисления факториала
Для рассмотренного выше рекурсивного алгоритма вычисления факториала количество вершин рекурсивного дерева равно, очевидно, n, при этом передается и возвращается по одному значению (m=1, k=1), в предположении о сохранении четырех регистров – r=4, а на последнем рекурсивном вызове значение функции вычисляется непосредственно – в итоге:
Отметим, что n – параметр алгоритма, а не количество слов на входе.
Источник
knigechka
Сайт содержит тексты редких методических пособий, лабораторных и контрольных работ. Вообщем, то что трудно найти в сети но очень нужно для подготовки к экзаменам, в частности на заочной форме обучения.
1.2. Рекурсивные функции
Исторически первой алгоритмической системой была система, основанная на использовании конструктивно определяемых арифметических (целочисленных) функций, получивших специальное название рекурсивных функций.
На проблемном уровне рекурсия может быть определена как возможность алгоритмической системы на промежуточном этапе своего функционирования создавать другие системы, включая идентичные себе самой, и использовать результаты их функционирования в дальнейшей работе.
Глубина вложенности обращений системы к самой себе допускается сколь угодно большой.
Существуют разнообразные формы задания и проявления рекурсии.
В математике рекурсивные методы присутствуют практически во всех областях. Одно из классических математических определений алгоритма базируется на теории рекурсивных функций. Рекурсивные методы повсеместно используются в исследованиях по искусственному интеллекту, в программировании в вычислительных алгоритмах и в задачах проектирования сложных систем.
При достаточно широкой трактовке понятия алгоритмической системы концепция рекурсивности отражает основные формы развития материи и является одним из важнейших методов познания.
Наиболее ярко рекурсивность проявляется в процессе развития человека и человечества в целом. Информация, содержащаяся в клетке, кодирует информацию о всем организме. Дети «повторяют» своих родителей, а общество и материя развиваются по сложной рекурсивной спирали.
Хорошей иллюстрацией к сказанному могут служить следующие высказывания о рекурсии в природе: «В песчинке или капле, как в микрокосмосе, отражается общий состав космоса. В ней могут быть найдены все те же элементы, какие наблюдаются на земном шаре, в небесных пространствах…»( 1909г. В.И. Вернадский)
Или в стихотворении В.Я. Брюсова «Мир электрона» звучат те же мотивы:
« Быть может эти электроны –
Миры, где пять материков,
Искусства, знанья, войны, троны
И память сорока веков.
Вселенная, где сто планет,
Там все, что здесь,
В объеме сжатом,
Но также то, чего здесь нет».
Рекурсия удобна для задания алгоритмов, а в некоторых случаях это единственно возможный способ определения сложного преобразования.
Понятие рекурсии необходимо разработчикам и пользователям сложных алгоритмических средств. Вместе с тем рекурсивные алгоритмы трудны в реализации и недостаточно исследованы теоретически.
В научной литературе приведено много результатов, посвященных рекурсии в программировании или в теории алгоритмов. Эта проблема является одной из наиболее «горячих точек» методологии программирования.
Дадим математическое определение рекурсии.
Рекурсией называется способ задания функции, при котором значение определяемой функции для произвольных значений аргументов выражается через значения определяемой функции для меньших значениях аргументов.
Численные функции, значение которых можно установить посредством алгоритма, называются вычислимыми функциями.
Функция называется рекурсивной, если существует эффективная процедура для ее вычисления.
Понятие эффективной процедуры является интуитивным. Говорят, что имеется эффективная процедура для выполнения определенных вычислений, если эти вычисления выполняются по механическим правилам, то есть по определенному алгоритму.
Поскольку понятие алгоритма в этом определении берется в интуитивном смысле, то и понятие вычислимой функции оказывается интуитивным.
Тем не менее, при переходе от алгоритмов к вычислимым функциям возникает одно очень существенное обстоятельство: совокупность процессов, подпадающих под понятие алгоритма очень обширна и мало обозрима. Совокупность вычислимых функций для самых разных пониманий процессов оказалась одной и той же и притом легко описываемой в обычных математических терминах.
Совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций при самом широком понимании алгоритма, носит название совокупность рекурсивных функций.
В 1936г. математиком Чёрчем была сформулирована гипотеза о том, что класс рекурсивных функций тождественен классу всюду определенных вычислимых функций.
Эта гипотеза известна под именем тезиса Чёрча.
Понятие вычислимой функции точно не определяется, поэтому тезис Чёрча доказать нельзя. В дальнейших рассуждениях нам потребуются некоторые определения, которые введены ниже.
Если некоторым элементам массива Х поставить в соответствие однозначно определенные элементы множества У то говорят что задана частичная функция из Х в У.
Совокупность тех элементов множества Х у которых есть соответствующие элементы в У, называется областью определенности функции, а совокупность этих элементов множества У – совокупностью значений функции.
 |
| |
Х-‘- = x-e, при x>=y
