Рекурсия

Компьютерные системы и сети
Лектор: к.т.н., доцент
Ничушкина Татьяна

Николаевна

Информатика
2008

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

Эта форма называется рекурсивной или индуктивной.
Любое рекурсивное утверждение строится с помощью двух утверждений, символизирующих собой две независимые части рекурсивного определения.
Первое утверждение носит названия базисного. Именно оно служит признаком завершения рекурсивной процедуры и является не рекурсивным.
Второе утверждение носит название рекурсивного. Рекурсивное утверждение записывается так, чтобы при цепочке повторных применений оно редуцировалось к базовому.
Например: определить понятие нечетное число
Базисное утверждение: 1 нечетное число.
Рекурсивное утверждение: Если I является нечетным, то нечетными являются числа, определяемые выражениями I-2, I+2 .

число.
7-2 ->5 5-2 -> 3 3-2-> 1

1 -> нечетное -> 3 -> 5 -> 7 – нечетное.
База указывает один или более случаев, удовлетворяющих определению.
Рекурсивная часть показывает, как надо применить определение, что бы проверить, удовлетворяют ли ему другие случаи.
Но есть еще и неявная часть рекурсии, которая, по умолчанию, утверждает, что никакие другие объекты не удовлетворяют определению.
Пример: Написать рекурсивное определение возведения числа x в степень n:
Базисное утверждение x0=1;
Рекурсивное утверждение
xn=x*xn-1;
Определим 35
35= 34*3
34= 33*3 …….

35

34

32

33

243

31

30

* 3

* 3

* 3

* 3

1

3

9

27

81

* 3

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

примером линейной рекурсии является вычисление факториала числа:
База 1!=1; 0!=1; Рекурсивное: N!=N*(N-1)!
Однако, есть рекурсивные определения, при вычислении по которым, на каждом уровне необходимо вычисление двух выражений, требующих дополнительного вычисления.
Пример: числа Фибоначчи 1 1 2 3 5 8 13 21 34 55 89 ….
Базисное утверждение: F1=1 и F2=1
Рекурсивное Fn=Fn-1+Fn-2
Найдем значение 5 числа Фибоначчи:
F5=F4 + F3;
F4=F3+F2 F3=F2+F1;
F3=F2+F1 F2=1; F1=1;
F2=1, F1=1.

F5

F4

F3

F2

F3

F1

F2

F2

F1

1

1

2

1

1

1

3

2

5

или функция обращается к самой себе.
Различают: явную и косвенную рекурсии.

При явной – в теле подпрограммы существует вызов самой себя, при косвенной – вызов осуществляется в подпрограммах, вызываемых из рассматриваемой.
Косвенная рекурсия требует предопределения:
void B(int j);
void A(int k);
{ ...B(i);...
}
void B(int j);
{... A(j);...
}

funstep(int x,int n)
{ if (n==0) return 1;

else
{return x*funstep(x,n-1);}
}
int

main(int argc, char* argv[])
{int x,n;
puts("input x,n for x^n");
scanf("%d %d",&x,&n);
printf("\n %7d ^ %3d =",x,n);
printf("%10d\n",funstep(x,n));
return 0;
}

funstep

n==0

funstep=1

return

funstep= x*funstep(x,n-1)

нет

да

Заголовок

Вызов рекурсивной функции

Рекурсивное утверждение

Базисное утверждение

int fib(int n)
{if((n==1)||(n==2)) return 1;

else
{ return fib(n-1)+ fib(n-2);}
}
int main(int argc,

char* argv[])
{int n;
puts("input n value Fibonnachi");
scanf("%d",&n);
printf("\n %7d Fibonachi =",n);
printf("%10d\n",fib(n));
return 0;
}

fib(n)

n=1 или n=2

fib=1

fib=fib(n-1)+fib(n-2)

return

нет

да

Заголовок

Рекурсивное утверждение

Вызов функции

Базисное утверждение

числа равны, то их наибольший общий делитель равен этим числам.
Рекурсивное

утверждение: наибольший общий делитель двух чисел равен наибольшему общему делителю их разности и меньшего из чисел.

a,int b)
{if(a==b) return a;
else
{ if (a>b) return nod(a-b,b);

else return nod(a,b-a);
}
}
int main(int argc, char* argv[])
{int a,b;
puts("input two integer value ");
scanf("%d %d",&a,&b);
printf("\n nod %7d %7d = %7d\n",a,b,nod(a,b));
return 0;
}

Базисное утверждение

Рекурсивное утверждение

Вызов рекурсивной функции

a,int b,int &r)
{if(a==b) r=a;
else
{ if (a>b)nod(a-b,b,r);
else nod(a,b-a,r);
}
}
int main(int

argc, char* argv[])
{int a,b,r;
puts("input two integer value ");
scanf("%d %d",&a,&b);
nod(a,b,r);
printf("\n nod %7d %7d = %7d\n",a,b,r);
return 0;
}

Заголовок процедуры с параметром переменной (ссылка)

Базисное утверждение

Рекурсивное утверждение

Вызов подпрограммы

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

активации рекурсивной подпрограммы, называется фреймом активации.
Фрейм активации включает
локальные переменные подпрограммы;
копии параметров-значений;
адреса параметров-переменных и параметров-констант (4 байта);
копию строки результата (для функций типа string);
служебную информацию (≈12 байт, точный размер этой области зависит от способа передачи параметров).

в конец результирующей строки: (Ex9_5)







char * reverse (char * s)
{

char s1[2],* ptr=s;
if (strlen(s)==0){s[0]='\0';return s;}
else
{s1[0]=s[0];s1[1]='\0';
return strcat(reverse(strcpy(s,ptr+1)),s1);}
}
Фрейм активации: V=4 + 2+4+256 + <служебная область> ≈278.

S=‘ABC’

S=‘ABC’

S=‘BC’

S=‘С’

S=‘’

Result:=… +S[1]

Result:=…+S[1]

Result:=…+S[1]

Result:=‘’

Заголовок функции

Базисное утверждение

Рекурсивное утверждение

reverse (char * s,int n)
{char temp;
if (n

temp=s[n];
s[n]=s[strlen(s)-n-1];
s[strlen(s)-n-1]=temp;
reverse(s,n+1);
}
}
Фрейм активации: V=4+4+1+<служебная область>≈21

Заголовок процедуры

Рекурсивная часть

Базисная подразумевается (ELSE)

величина функции в середине отрезка не превышает заданного значения погрешности,

то координата середины отрезка и есть корень.
Рекурсивное утверждение: Корень расположен между серединой отрезка и тем концом, значение функции в котором по знаку не совпадает со значением функции в середине отрезка.

#include
void root(float a,float b,float eps,float &r)
{float x,f;
x=(a+b)/2;
f=x*x-1;

if (fabs(f)>=eps)
if ((a*a-1)*f>0)
root(x,b,eps,r);
else
root(a,x,eps,r);
else r=x;
}

Заголовок рекурсивной процедуры

Рекурсивное утверждение

Базисное утверждение
fabs(f)

Рекурсивный вызов

Если корней на заданном отрезке нет, то произойдет зацикливание!

argc, char* argv[])
{ float a,b,eps,r;
puts("Input a,b,eps");
scanf("%f %f %f",&a,&b,&eps);
if

((a*a-1)*(b*b-1)<0)
{root(a,b,eps,r);
printf("Root of X^2-1 na otrezke");
printf("%5.2f - %5.2f",a,b);
printf(" ravna %7.3f\n",r);}
else
{printf("Root of X^2-1 na otrezke");
printf("%5.2f - %5.2f",a,b);
printf(" is epsent \n");}
return 0;
}

Вызов подпрограммы

Для предотвращения зацикливания в подпрограмме, в основной программе – проверка наличия корней

рекурсивно вызванной подпрограммы.

Пример. Распечатать положительные элементы массива в порядке следования,

а отрицательные элементы – в обратном порядке. Признак конца массива – 0.

нулей
в середине, например:

4 -5 8 9 -3 0.
Необходимо напечатать положительные элементы в том порядке, как они встречаются в массиве и отрицательные элементы в обратном порядке:
4 8 9 -3 -5

i)
{if (x[i]==0) puts("***********");
else
{if (x[i]>0)printf("%4d\n",x[i]);
print(x,i+1);
if

(x[i]<0)printf("%4d\n",x[i]);
}
}

Заголовок рекурсивной подпрограммы

Базисное утверждение

Операторы до рекурсивного вызова

Операторы после рекурсивного вызова

Рекурсивный вызов п/п

puts("input massiv v konce 0");
i=-1;
do
{i=i+1;

scanf("%d",&x[i]);
}while (x[i]!=0);
puts(" RESULT ");
print(x,0);
return 0;
}

Вызов рекурсивной подпрограммы в программе

формирования перестановок:

r[],int pole[])
{int r1[3],k,i,j;
if (n==m){
for(i=0;i

perest(n+1,m,r1,pole);
}
}
//Основная программа
int main(int argc, char* argv[])
{ int a[3]={5,6,7},pole[3];
perest(0,3,a,pole);
return

0;
}

Рекурсивный вызов

Вызов рекурсивной
подпрограммы

N*N так, чтобы они не били друг друга.

















Условие того, что

ферзь «бьет другого»:
Pole[ j ]=Pole[ i ] – одна горизонталь;
|Pole[ j ]-Pole[ i ] | = | j - i | – одна диагональ.

Pole

корректности варианта
int new_r(int n,int pole[])
{int r=1;
for(int j=0;j

pole[n])==abs(n-j)))
r=0;
return r;
}

Условие «один ферзь бьет другого»

Заголовок функции проверки варианта

pole[])
{ int i;
if (n==m){
for(i=0;i

printf("%2d",pole[i]+1);
printf("\n"); }
else
for(i=0;i {pole[n]=i;
if(new_r(n,pole)==1) ferz(n+1,m,pole);
}
}

Заголовок процедуры

Базисное утверждение

Вызов рекурсивной процедуры из рекурсивной части подпрограммы

scanf("%d",&m);
ferz(0,m,pole);
return 0;}

Вызов рекурсивной подпрограммы