uzluga.ru
добавить свой файл


Рекурсия Rekursioon


В окружающем нас мире часто можно встретить объекты, обладающие самоподобием. То есть часть большого объекта в чем-то сходна с самим объектом. Например, ветка дерева повторяет форму и характер ветвления, схожие с самим деревом.

В окружающем нас мире часто можно встретить объекты, обладающие самоподобием. То есть часть большого объекта в чем-то сходна с самим объектом. Например, ветка дерева повторяет форму и характер ветвления, схожие с самим деревом.

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

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

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

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

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

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

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

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

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

Рекурсия в широком смысле – это определение объекта посредством ссылки на себя.

Рекурсия в программировании – это пошаговое разбиение задачи на подзадачи, подобные исходной.

Рекурсивный алгоритм это алгоритм, в определении которого содержится прямой или косвенный вызов этого же алгоритма.

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

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

Пример 1.

В арифметической прогрессии найдите an, если известны а1 = -2.5, d=0.4,

не используя формулу n-го члена прогрессии.

По определению арифметической прогрессии, an=an-1+d, при этом

an-1=an-2+d, an-2=an-3+d,... a2=a1+d.

Таким образом, нахождение an для номера n сводится к решению аналогичной задачи, но только для номера n-1, что в свою очередь сводится к решению для номера n-2, и так далее, пока не будет достигнут номер 1 (значение а1 дано по условию задачи).

float arifm (int n, float a, float d)

{

if (n<1) return 0; // для неположительных номеров

if (n= =1) return a; // базовый случай: n=1

return arifm(n-1,a,d)+d; // общий случай

}

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

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

В программировании выделяют прямую и косвенную рекурсию.

Прямая рекурсия - непосредственное обращение рекурсивной функции к себе, но с иным набором входных данных.

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

Для решения задач рекурсивными методами разрабатывают следующие этапы, образующие рекурсивную триаду:

Для решения задач рекурсивными методами разрабатывают следующие этапы, образующие рекурсивную триаду:
  • параметризация – выделяют параметры, которые используются для описания условия задачи, а затем в решении;

  • база рекурсии – определяют тривиальный случай, при котором решение очевидно, то есть не требуется обращение функции к себе;

  • декомпозиция – выражают общий случай через более простые подзадачи с измененными параметрами.



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

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

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

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

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

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

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

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

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

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

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









Функция S(n) вычисляет сумму первых n положительных чисел. Funktsioon S(n) arvutab esimese n positiivse arvu.



Для вычисления S(11) нужно взять предыдущий результат (55) и прибавить к нему 11. Это называется рекурсивным процессом. Arvutamisel S(11) on vaja võtta eelmine tulemus (55) ja liita 11. See protsess nimetatakse rekursiooniks.



Определим степенную функцию xn, где х – действительное число, а n – неотрицательное число. Funktsiooni xn determineerimine (x on reaalarv ja n on positiivne arv). Xn = x * x * x *…* x



Для хn можно определить рекурсивное выражение Rekursiooniline avaldis astelise funktsiooni xn on



Ханойская башня.

Ханойская башня.





















Вычисление факториала числа

Factorial (n) = 1 * 2 * 3 * …* (n-2) * (n-1) * n

Factorial (4) = 1 * 2 * 3 * 4 = 24

Factorial (6) = 1 * 2 * 3 * 4 * 5 * 6 = 720

Factorial (1) = 1 * Factorial (0) = 1

Factorial (0) = 1



n!=



Схема вызовов функции Factorial.



//Пример использования функции Factorial. long Factorial (long n) { if (n==0) return 1; else return n*Factorial (n-1); } void main(void) { int i, n; cin>>n; cout<











Задание

Числа Фибоначчи:

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