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

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

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

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

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

Источник

BestProg

Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии

Содержание

Поиск на других ресурсах:

1. Что такое рекурсия? Что называется рекурсией?

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

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

2. Объяснение к реализации задач на рекурсию. Как правильно организовать рекурсивный вызов функции?

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

Чтобы циклический процесс превратить в рекурсивный, нужно уметь определить (выделить) три важных момента:

• условие прекращения рекурсивного процесса. Например, если счетчик или итератор с именем k изменяется от 1 до 10 в возрастающем порядке, то условие прекращения есть достижение значения k =10. Условие прекращения указывается в операторе return ;
• формулу следующего элемента или итератора, который используется в рекурсивном процессе. Эта формула указывается в операторе return ;
• перечень параметров, которые передаются в рекурсивную функцию. Один из параметров обязательно есть итератор (счетчик), изменяющий свое значение. Другие параметры являются дополнительными, например, ссылка на обрабатываемый массив.

3. Поиск суммы элементов массива. Пример

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

Задача. Задан массив чисел A . Разработать рекурсивную функцию, которая находит сумму элементов массива:

где n – количество элементов массива. Программный код функции следующий:

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

Последний элемент массива имеет индекс A.length-1 . Достижение функцией последнего элемента массива есть выходом из нее. Поэтому, в тексте функции Sum() указывается условие прекращения рекурсивного процесса:

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

Поскольку, осуществляется сумма текущего значения A[i] со следующими, то указывается строка

где Sum(i+1, A) означает следующее значение массива A , которое будет вычислено на следующем (нижнем) уровне рекурсивного вызова. Параметр i+1 указывает, что на следующем уровне рекурсии будут взяты следующий за данным элемент массива.

Использование функции Sum() в другом программном коде может быть следующим:

4. Вычисление факториала числа – n! . Пример

В примере разработана рекурсивная функция, которая находит факториал заданного числа n

Программный код функции следующий:

В данной функции происходит рекурсивный вызов функции Fact() с параметром n , который изменяется от n до 1 в порядке убывания. Рекурсивный процесс завершается при n = 1.

При возврате на уровень выше возвращается текущее значение n и результат вычислений при следующих рекурсивных вызовах:

Использование функции в другом программном коде:

5. Программа нахождения наибольшего общего делителя по алгоритму Евклида. Пример

В примере определяется наибольший общий делитель по формуле Евклида:

Программный код функции следующий:

Использование функции MaxDivisor

6. Вычислить n -й член последовательности чисел Фибоначчи. Пример

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

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

В последовательности чисел Фибоначчи каждое следующее число n определяется как сумма двух предшествующих чисел: (n-1) + (n-2) . Поэтому, в формуле рекурсивного процесса может быть вызов суммы двух функций а не одной. Прекращение рекурсивного процесса достигается, если значение n =0.

Ниже приведен текст функции GetNFibonacci()

Использование метода GetNFibonacci() в другом программном коде:

7. Преимущества и недостатки использования рекурсии

Рекурсию часто сравнивают с итерацией. Организация циклического процесса с помощью рекурсии имеет свои преимущества и недостатки.

Можно выделить следующие взаимосвязанные преимущества рекурсии:

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

Недостатки рекурсии состоят в следующем:

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

Источник

BestProg

Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии

Содержание

Поиск на других ресурсах:

1. Что такое рекурсия? Что называется рекурсией?

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

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

2. Объяснения к реализации задач на рекурсию. Как правильно организовать рекурсивный вызов функции?

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

Чтобы циклический процесс преобразовать в рекурсивный, нужно уметь определить (выделить) три важных момента:

• условие прекращения последовательности рекурсивных вызовов функции. Например, если счетчик или итератор с именем k изменяется от 1 до 10 в возрастающем порядке, то условие прекращения есть достижение значения k =10. Условие прекращения указывается в операторе return ;
• формулу следующего элемента или итератора, который используется в рекурсивном процессе. Эта формула указывается в операторе return ;
• список параметров, которые передаются в рекурсивную функцию. Один из параметров обязательно есть итератор (счетчик) изменяющий свое значение. Другие параметры являются дополнительными, например, ссылка на массив, над которым осуществляется обработка.

3. Поиск суммы элементов массива. Пример

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

Задача. Задан массив чисел A . Разработать рекурсивную функцию, которая находит сумму элементов массива:

где n – количество элементов массива. Программный код функции следующий:

Как видно из примера, в рекурсивную функцию Sum() передается 3 параметра:

• текущее значение итератора i ;
• массив A ;
• количество элементов массива n .

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

Для суммирования текущего значения A[i] со следующими указывается строка:

где рекурсивный вызов Sum(i+1, A, n) означает следующее значение массива A . Параметр i+1 указывает, что на следующем уровне вызова рекурсивной функции будет взят следующий после данного элемент массива.

Использование функции Sum() в другом программном коде может быть, например, таким:

4. Пример подсчета количества вхождений заданного символа в строке

В данном примере реализована рекурсивная функция Count() , которая определяет количество вхождений заданного символа c в строке s . Функция получает 3 параметра:

• символ c , который нужно сравнить с каждым символом строки s ;
• строка s ;
• дополнительная переменная i , которая есть счетчиком рекурсивного цикла.

Реализация функции Count() следующая:

5. Пример нахождения факториала числа – n!

Вычисление факториала числа методом рекурсии есть почти в каждом учебнике. Факториал числа вычисляется по формуле

Рекурсивный вызов можно организовать двумя способами:

• в порядке возрастания 1, 2, …, n ;
• в порядке убывания n , n -1, …, 2, 1.

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

В первую функцию Fact1() передаются 2 параметра. Первый параметр определяет максимально возможное значение n , которое может быть умножено. Второй параметр определяет текущее значение i которое умножается.

Во второй функции Fact2() передается 1 параметр – максимально возможное значение n , принимающее участие в рекурсивном умножении. Второго параметра здесь не нужно, поскольку условие прекращения рекурсивного процесса есть известно и равно 1. В функции Fact2() рекурсивный процесс завершается при n =1.

Использование функций в другом программном коде может быть следующим:

6. Программа нахождения наибольшего общего делителя (алгоритм Евклида). Пример

В примере определяется наибольший общий делитель по формуле Евклида:

Программный код функции следующий:

Использование функции MaxDiv() может быть следующим:

7. Подсчет количества элементов массива, больших заданного числа. Пример

Демонстрируется метод Count() , возвращающий количество элементов, больших заданного числа num . В метод передается 4 параметра:

• число num , которое нужно сравнивать с каждым элементом массива;
• массив чисел A[ ] ;
• количество элементов массива n ;
• текущее значение счетчика в массиве.

Использование метода Count() в другом методе

8. Преимущества использования рекурсии в программах. Пример

Рекурсию часто сравнивают с итерацией. Организация циклического процесса с помощью рекурсии имеет свои преимущества и недостатки.

Можно выделить следующие взаимосвязанные преимущества рекурсии:

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

Недостатки рекурсии состоят в следующем:

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

Источник