Это функция которая обращается сама к себе

Рекурсия

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

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

 ::= |   ::= 0 | 1

Здесь для описания понятия были использованы, так называемые, металингвистический формулы Бэкуса-Наура (язык БНФ); знак «::=» обозначает «по определению есть», знак «|» — «или».

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

Приведём другие примеры рекурсивных определений.

Пример 1. Классический пример, без которого не обходятся ни в одном рассказе о рекурсии, — определение факториала. С одной стороны, факториал определяется так: n !=1*2*3*. * n . С другой стороны, Граничным условием в данном случае является n Пример 2. Определим функцию K(n) , которая возвращает количество цифр в заданном натуральном числе n :

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

Пример 3. Функция C(m, n) , где 0 m n , для вычисления биномиального коэффициента по следующей формуле является рекурсивной.

Ниже будут приведены программные реализации всех этих (и не только) примеров.

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

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

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

Begin Begin Begin P; операторы; операторы; операторы; P P; End; End; операторы End; рекурсивный подъём рекурсивный спуск и рекурсивный спуск, и рекурсивный подъём

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

Реализуем приведённые выше рекурсивные определения в виде функций и процедур на языке Pascal и в виде функций на языке C.

 Function Factorial(N:integer):Extended; Begin If N
 Procedure Factorial(N:integer; Var F:Extended); Begin If N
/* Функция на C */ double Factorial(int N)
Пример 2.  
 Function K(N:Longint):Byte; Begin If N
 Procedure K(N:Longint; Var Kol:Byte) Begin If N
/* Функция на C */ int K(int N) < int Kol; if (N<10) Kol=1; else Kol=K(N/10)+1; return Kol; >
Пример 3.  
 function C(m, n :Byte):Longint; Begin If (m=0) or (m=n) Then C:=1 Else C:=C(m, n-1)+C(m-1, n-1) End;
 Procedure C(m, n: Byte; Var R: Longint); Var R1, R2 : Longint; Begin If (m=0) or (m=n) Then R:=1 Else Begin C(m, n-1, R1); C(m-1, n-1, R2); R:=R1+R2 End; End;
/* Функция на C */ int C(int m, int n)






Пример 4. Вычислить сумму элементов линейного массива.
При решении задачи используем следующее соображение: сумма равна нулю, если количество элементов равно нулю, и сумме всех предыдущих элементов плюс последний, если количество элементов не равно нулю.
 Program Rec2; Type LinMas = Array[1..100] Of Integer; Var A : LinMas; I, N : Byte; Function Summa(N : Byte; A: LinMas) : Integer; Begin If N = 0 Then Summa := 0 Else Summa := A[N] + Summa(N - 1, A) End; Begin Write('Количество элементов массива? '); ReadLn(N); Randomize; For I := 1 To N Do Begin A[I] := -10 + Random(21); Write(A[I] : 4) End; WriteLn; WriteLn('Сумма: ', Summa(N, A)) End.
/* Программа на языке C */ #include #include #include #include int summa(int N, int a[100]); int i,n, a[100]; void main() < clrscr(); printf("\nКоличество элементов массива? "); scanf("%d", &n); printf("\nВ сформированном массиве %d чисел:\n", n); randomize(); for (i=0; iprintf("Сумма: %d", summa(n-1, a)); > int summa(int N, int a[100])
Пример 5. Определить, является ли заданная строка палиндромом, т.е. читается одинаково слева направо и справа налево.






Идея решения заключается в просмотре строки одновременно слева направо и справа налево и сравнении соответствующих символов. Если в какой-то момент символы не совпадают, делается вывод о том, что строка не является палиндромом, если же удается достичь середины строки и при этом все соответствующие символы совпали, то строка является палиндромом. Граничное условие — строка является палиндромом, если она пустая или состоит из одного символа.
 Program Palindrom; Function Pal(S: String) : Boolean; Begin If Length(S) Begin Write('Введите строку: '); ReadLn(S); If Pal(S) Then WriteLn('Строка является палиндромом') Else WriteLn('Строка не является палиндромом') End.
/* программа на языке C */ #include #include #include char s[100]; int pal(char s[100]); void main() < clrscr(); printf("\nВведите строку: "); gets(s); if (pal(s)) printf("Строка является палиндромом"); else printf("Строка не является палиндромом"); >int pal(char s[100]) < int l; char s1[100]; if (strlen(s)<=1) return 1; else >
Задание. Используя аналогичный подход, определите, является ли заданное натуральное число палиндромом.
Подводя итог, заметим, что использование рекурсии является красивым приёмом программирования. В то же время в большинстве практических задач этот приём неэффективен с точки зрения расходования таких ресурсов ЭВМ, как память и время исполнения программы. Использование рекурсии увеличивает время исполнения программы и зачастую требует значительного объёма памяти для хранения копий подпрограммы на рекурсивном спуске. Поэтому на практике разумно заменять рекурсивные алгоритмы на итеративные.






Контрольные вопросы и задания

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

Function Stroka : String; Var C : Char; Begin Write('Введите очередной символ: '); ReadLn(C); Stroka:=Stroka+C End;
Это функция которая обращается сама к себе
Одну и ту же задачу можно часто решить двумя способами: с помощью итерации (с использованием цикла) и с помощью рекурсии. Рекурсия – это способ организации процесса вычисления, когда алгоритм (функция или процедура программы) обращается сам к себе.
В математике рекурсивной называется функция, имя которой присутствует в обоих частях уравнения – как справа, так и слева.






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






Обычно рекурсивный алгоритм содержит следующие основные части:

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

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






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







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

Примером классической рекурсивной функции является возведение некоторого действительного числа X в степень N (Xn).
function TForm1.StepN(n: integer; x: single): single;
begin
if n=0 then 
StepN := 1 
else StepN := x*stepN(n-1, x);
end;
Программирование. Рекурсия Pascal-Паскаль
Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией.
Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшее обращение к подпрограмме не происходит.






Пример.
Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».
Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.
Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.






Применение рекурсии позволило решить задачу без использования циклов, как в основной программе, так и в процедуре.
Пример программы с использованием рекурсии 
Program Arsac; 
Var first: word; 
Procedure posledov (i: word); 
Begin 
Writeln (i); 
If i=1 then exit; 
If odd(i) then posledov(3*i+1) else posledov(i div 2); 
End; 
Begin 
Write (' введите первое значение '); readln (first); 
Posledov (first); 
Readln ; 
End.
Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F( N) может понадобиться вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.






Алгоритм, который является своей собственной частью, называется рекурсивным. Часто в основе такого алгоритма лежит рекурсивное определение.
Пример рекурсивного алгоритма 
N! = ( N-1)!* N, если N=0, то N!= 1
Любое рекурсивное определение состоит из двух частей. Одна часть определяет понятие через него же, другая часть – через иные понятия.






Пример рекурсивного алгоритма 
2n= 2 n-1*2, если n=0, то 2 n= 1
Процедура является рекурсивной, если она обращается сама к себе прямо или косвенно (через другие процедуры).






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






Function factorial(N: integer) : longint; 
Begin 
If N= 0 then 
Factorial := 1 
Else Factorial := factorial(N-1) * N 
End;
Рекурсия изнутри
Это может показаться удивительным, но самовызов процедуры ничем не отличается от вызова другой процедуры. Что происходит, если одна процедура вызывает другую? В общих чертах следующее:

в памяти размещаются параметры, передаваемые процедуре (но не параметры-переменные!);
в другом месте памяти сохраняются значения внутренних переменных вызывающей процедуры;
запоминается адрес возврата в вызывающую процедуру;
управление передается вызванной процедуре.

Если процедуру вызвать повторно из другой процедуры или из нее самой, будет выполняться тот же код, но работать он будет с другими значениями параметров и внутренних переменных. Это и дает возможность рекурсии.
Пусть рекурсивная процедура Power( X, N, Y) возводит число X в степень N и возвращает результат Y .
Пример рекурсивной процедуры, возводящей число в степень 
Procedure Power (X: real; N: integer; var Y: real); 
Begin 
If N=0 then 
Y:= 1 
Else Begin Power(X, N-1,Y); 
Y:= Y*X; 
End ; 
End ;
Проследим за состоянием памяти в процессе выполнения вызова данной процедуры Power(5,3, Y). Стрелка «->» означает вход в процедуру, стрелка « 0 then 
begin 
xn:=(x1+x2) div 2 +(y2-y1) div 2; 
yn:=(y1+y2) div 2 -(x2-x1) div 2; 
ris(x1,y1,xn,yn,k-1); 
ris(x2,y2,xn,yn,k-1); 
end 
else begin line(x1,y1,x2,y2); end; 
end; 
begin 
readln ( k );  
d:=detect; 
initgraph(d,m,'e:\bp\bgi'); 
ris(200,300,500,300,k); 
readln; 
end.
Программирование
Исходники Pascal (127)
Справочник
Справочник по паскалю: директивы, функции, процедуры, операторы и модули по алфавиту
3. Рекурсивная функция
Вспомним: числа Фибоначчи — это числовой ряд, где каждый последующий элемент получается путём сложения двух предыдущих.
Ряд Фибоначчи:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 .

Опишем рекурсивную функцию.

function Fib (N: integer): integer;

begin

if (N: \(=\) \(1\) ) or (N: \(=\) \(2\) ) then

Fib: \(=\) \(1\)

else Fib: \(=\) Fib (N \(-\) \(1\) ) \(+\) Fib (N \(-\) \(2\) );
Если порядковый номер числа \(1\) или \(2\), то мы указываем, что они равны единице. Вычисление остальных чисел Фибоначчи записываем после else: сумма двух предыдущих чисел.

Рекурсивная функция работает по нисходящему и восходящему принципу.
Чтобы вычислить \(10\)-й элемент последовательности функции, нужно знать значения \(9\)-го и \(8\)-го элементов, потому что:
\(F (10) = F(9) + F(8)\);

\(F (9) = F(8) + F (7)\);
\(F (8) = F(7)+F(6)\) и т. д., пока функция не дойдёт до самого первого элемента, после чего будет подниматься вверх и складывать все получившиеся числа.


Похожие публикации:

Com google android gms что это
Как ставить блок питания кулером вверх или вниз
Как убрать белый курсор в pycharm
Что делать после прохождения