Что такое рекурсивный способ задания функции

а) Терминологическое введение

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

Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при 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г. математиком Чёрчем была сформулирована гипотеза о том, что класс рекурсивных функций тождественен классу всюду определенных вычислимых функций.

Эта гипотеза известна под именем тезиса Чёрча.

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

Если некоторым элементам массива Х поставить в соответствие однозначно определенные элементы множества У то говорят что задана частичная функция из Х в У.

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

Если область определенности функции из Х в У совпадает с множеством Х, то функция называется всюду определенной.

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

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

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

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

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

После нумерации входных и выходных слов в произвольном алфавитном операторе, этот оператор превращается в функцию У=f(Х), в которой аргумент Х и функция У принимают неотрицательные целочисленные значения.

Функция f(Х) может быть определена не для всех значений Х, а лишь для тех, которые составляют область определения этой функции. Подобные частично определенные целочисленные и целозначные функции называются арифметическими функциями. Среди них выделим наиболее простые и будем их называть элементарными арифметическими функциями:

1.Функции тождественно равные нулю

определенные для всех неотрицательных значений аргументов;

2.Тождественные функции, повторяющие значения своих аргументов:

I_ni(x₁,x₂,…x_n)=x_i (1 =y, так как отрицательные числа не входят в рассматриваемую область. Но примитивно рекурсивные функции всюду определены. Поэтому в теории примитивных рекурсивных функций вместо обычной разности вводят усеченную разность, обозначаемую -‘-, и определенную следующим образом:

Х-‘- = x-e, при x>=y

0, x Автор: Vadik на суббота, октября 24, 2009

Источник

Как работает рекурсия – объяснение в блок-схемах и видео

Представляю вашему вниманию перевод статьи Beau Carnes How Recursion Works — explained with flowcharts and a video.

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

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

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

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

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

Какой подход для Вас проще?

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

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

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

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

Граничный и рекурсивный случай

То, что Вам необходимо принять во внимание при написании рекурсивной функции – это бесконечный цикл, т.е. когда функция вызывает саму себя… и никогда не может остановиться.
Допустим, Вы хотите написать функцию подсчета. Вы можете написать ее рекурсивно на Javascript, к примеру:

Эта функция будет считать до бесконечности. Так что, если Вы вдруг запустили код с бесконечным циклом, остановите его сочетанием клавиш «Ctrl-C». (Или, работая к примеру в CodePen, это можно сделать, добавив “?turn_off_js=true” в конце URL.)

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

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

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

Сначала мы выведем цифру 5, используя команду Console.Log. Т.к. 5 не меньше или равно 1, то мы перейдем в блок else. Здесь мы снова вызовем функцию и передадим в нее цифру 4 (т.к. 5 – 1 = 4).

Мы выведем цифру 4. И снова i не меньше или равно 1, так что мы переходим в блок else и передаем цифру 3. Это продолжается, пока i не станет равным 1. И когда это случится мы выведем в консоль 1 и i станет меньше или равно 1. Наконец мы зайдем в блок с ключевым словом return и выйдем из функции.

Стек вызовов

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

Я продемонстрирую Вам стек вызовов в действии, используя функцию подсчета факториала. Factorial(5) пишется как 5! и рассчитывается как 5! = 5*4*3*2*1. Вот рекурсивная функция для подсчета факториала числа:

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

Заметили, как каждое обращение к функции fact содержит свою собственную копию x. Это очень важное условие для работы рекурсии. Вы не можете получить доступ к другой копии функции от x.

Нашли уже ключ?

Давайте кратенько вернемся к первоначальному примеру поиска ключа в коробках. Помните, что первым был итеративный подход с использованием циклов? Согласно этому подходу Вы создаете стопку коробок для поиска, поэтому всегда знаете в каких коробках вы еще не искали.

Но в рекурсивном подходе нет стопки. Так как тогда алгоритм понимает в какой коробке следует искать? Ответ: «Стопка коробок» сохраняется в стеке. Формируется стек из наполовину выполненных обращений к функции, каждое из которых содержит свой наполовину выполненный список из коробок для просмотра. Стек следит за стопкой коробок для Вас!

И так, спасибо рекурсии, Вы наконец смогли найти свой ключ и взять рубашку!

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

Заключение от автора

Надеюсь, что статья внесла немного больше ясности в Ваше понимание рекурсии в программировании. Основой для статьи послужил урок в моем новом видео курсе от Manning Publications под названием «Algorithms in Motion». И курс и статься написаны по замечательной книге «Grokking Algorithms», автором которой является Adit Bhargava, кем и были нарисованы все эти замечательные иллюстрации.

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

От себя хочу добавить, что с интересом наблюдаю за статьями и видеоуроками Beau Carnes, и надеюсь что Вам тоже понравилась статья и в особенности эти действительно замечательные иллюстрации из книги A. Bhargav «Grokking Algorithms».

Источник