Рекурсивные подпрограммы

(подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе

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

Например, приведенное ниже определение двоичного кода является рекурсивным:
<двоичный код> ::= <двоичная цифра> | <двоичный код><двоичная цифра>
<двоичная цифра> ::= 0 | 1
Здесь для описания понятия были использованы, так называемые, металингвистический формулы Бэкуса-Наура (язык БНФ); знак "::=" обозначает "по определению есть", знак "|" – "или".

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

И+ПРГ

Практическое занятие

прогрессии:
/* Вычисление суммы K членов ряда арифметической прогрессии
K -

количество суммируемых членов ряда,
N-шаг прогрессии,
FS - значение первого члена ряда */

int SUMpr(int K, int FS, int N) /* рекурсивная функция вычисления суммы членов ряда */
{
if(K==1) return FS;
return FS+(K-1)*N+SUMpr(K-1,FS,N); // рекурсивное выражение
}

void main()
{
int n,arg,ras;
cout<<"Введите количество суммируемых членов ряда n = ";
cin>>n;
cout<<"Введите значение первого члена ряда arg = ";
scanf ("%d", arg);
printf ("Введите шаг прогрессии ras = ");
scanf ("%d", ras);
cout<<"\nСумма членов ряда = "<< SUMpr(n,arg,ras);
getch();
}

И+ПРГ

Ньютона):
Xk+1 = ½ (Xk + a / Xk),
где a

– число, X0 – начальное приближение результата (например, можно X0=a).
Цикл вычисления завершаем, когда разность между двумя соседними членами последовательности становится меньше заданной константы (определяющей точность вычисления)

И+ПРГ

Pascal

program sqrtnewr;
Var x, y, eps: real;
 function SqrtNewton(x,y,eps: real) : real;
(* Рекурсивная функция вычисления квадратного корня - алгоритм Ньютона *)
begin
if abs(x/y-y) then SqrtNewton
else
SqrtNewton:=SqrtNewton(x,(x/y+y)/2, eps);
end;
 
begin
repeat
writeln(' Введите число x=');
readln(x);
writeln(' Введите точность eps=');
readln(eps);
until (x>0) and (eps>0);
y:=SqrtNewton(x,x/2,eps);
writeln(' Квадратный корень из ',x:6:2,' =', y:5:2);
end.

#include
#include
#include
float sqrtnewton (float N, float prev, float pr)
/* рекурсивная функция вычисления квадратного корня*/
{ if(abs(N/prev-prev) < pr)
return (N/prev+prev)/2;
return sqrtnewton (N, (N/prev+prev)/2, pr);
}

void main()
{ clrscr();
float A; // число из которого извлекается корень
float X; // член ряда - значение корня квадратного
float Xprev; // предыдущий член ряда, приближенный результат
float t; // заданная точность
do { cout<<"Введите число А > 0 \n"; cin >> A;
cout<<"Введите точность t > 0 \n"; cin >> t; }
while ((A<=0) && (t<=0)); Xprev = A/2;
X = sqrtnewton( A, Xprev, t);
 cout << "Значение квадратного корня числа " << A << " = " << X <<"\n"; getch();
}

C / C++

Вычисление рекурсией

факториал определяется так: n!=1*2*3*...*n.
С другой стороны,


И+ПРГ

Практическое занятие

C

Pascal

(* Функция на Pascal *)
Function Factorial (N:integer):Extended;
Begin
if N<=1 Then Factorial := 1
Else Factorial := Factorial (N-1) *N;
End;

Граничным условием в данном случае является n<=1.

(* Процедура на Pascal *)
Procedure
Factorial (N:inteqer; Var F:Extended);
Begin
if N<=1 Then F:=1
Else Begin
Factorial (N-1, F); F:=F*N;
End;
End;

/* Функция на С */
double Factorial (int N)
{
double F;
if (N<=1) F=1.0;
else F=Factorial(N-1)*N;
return F;
}

числе n
Определим функцию K(n):
И+ПРГ
Практическое занятие
C
Pascal
(* Функция на Pascal

*)
Function K (N:Longint) : Byte;
Begin
if N < 10
Then K := 1
Else K := K (N div 10) + 1;
End;

(* Процедура на Pascal *)
Procedure
K (N:Lonqint; Var Kol:Byte);
Begin
if N < 10
Then Kol := 1
Else Begin
K (N div 10, Kol); Kol := Kol + 1;
End;
End;

/* Функция на С */
int К (int N)
{
int Kol;
if (N <10 )
Kol = 1;
Kol = K ((int) N/10)+1;
return Kol;
}

задачи используем следующее рассуждение: сумма равна нулю, если количество элементов

равно нулю, и сумме всех предыдущих элементов плюс последний, если количество элементов не равно нулю.

И+ПРГ

Практическое занятие

C

Pascal

Program RecSumMas;
Type LinMas = -Array[l..100] of Inteqer;
Var A : LinMas; I, N : Byte;
(* Рекурсивная функция *)
Function Summa(N:Byte; A:LinMas):Integer;
Begin
if N=0 Then Summa :=
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.

#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("\nB массив введено %d чисел:\n", n);
randomize();
for (i=0; i { a[i] =--10+random(21);
printf("%d", a[i]);
}
printf ("Сумма: %d", summa (n-1, a)) ;
}
// Рекурсивная функция
int summa(int N, int a[100])
{ if (N==0) return 0;
else return a[N]+summa (N-1, a); }

заключается в просмотре строки одновременно слева направо и справа налево

и сравнении соответствующих символов. Если в какой-то момент символы не совпадают, деается вывод о том, что строка не является палиндромом, если же удается достичь середины строки и при этом все соответствующие символы совпали, то строка является палиндромом. Граничное условие ‒ строка является палиндромом, если она пустая или состоит из одного символа.

И+ПРГ

Практическое занятие

C

Pascal

Proqram Palindrom;
(* Рекурсивная функция *)
Function Pal (S: String) : Boolean;
Begin
if Length(S)<=1
Then Pal:=True
Else Pal:= (S[1]=S[Length(S)]) and
Pal(Copy(S, 2, Length(S)-2));
End;
(* Основная программа *)
Var S:String;
Begin
Write('Введите -строку: '); ReadLn(S);
If Pal(S) Then WriteLn('Строка является палиндромом') ;
Else WriteLn('Строка не
является палиндромом');
End.

#include
#include
#include
сhar s[100];
int pal(char s [100]);
void main () // Основная программа
{ сlrscr() ;
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 { L=s[0]==s [strlen (s)-1 ];
strncpy(sl, s + 1, 'strlen(s)-2) ;
s1 [strlen (s)-2] = '\0';
return L && pal(s1); }
}