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

Глава 9. Рекурсия

МГТУ им. Н.Э. Баумана
Факультет Информатика и системы управления
Кафедра Компьютерные системы и сети
Лектор: к.т.н., доцент
Ничушкина Татьяна Николаевна

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

Основные понятия (2)
Используя это определение, докажем. Что 7 – нечетное число.
7-2 ->5 5-2 -> 3 3-2-> 1 1 -> нечетное -> 3 -> 5 -> 7 – нечетное.
База указывает один или более случаев, удовлетворяющих
определению.
Рекурсивная часть показывает, как надо применить определение, что
бы проверить, удовлетворяют ли ему другие случаи.
Но есть еще и неявная часть рекурсии, которая, по умолчанию,
утверждает, что никакие другие объекты не удовлетворяют
определению.
Пример: Написать рекурсивное определение возведения числа x в
степень n:
243
81
35
Базисное утверждение x0=1;
34 * 3
27
Рекурсивное утверждение
33 * 3
9
n
n-1
x =x*x ;
32 * 3
3
Определим 35
31 * 3
1 30
35= 34*3
*3
3
4
3
3 = 3 *3 …….

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

Основные понятия(4)
Рекурсивная подпрограмма – организация вычислений, при которой
процедура или функция обращается к самой себе.
Различают: явную и косвенную рекурсии. При явной – в теле
подпрограммы существует вызов самой себя, при косвенной –
вызов осуществляется в подпрограммах, вызываемых из
рассматриваемой.
Косвенная рекурсия требует предопределения:
void

B(int j);
void A(int k);
{ ...B(i);...
}
void B(int j);
{... A(j);...
}
5

Вычисление целой степени целого числа
// Ex9_1.cpp
Заголовок
funstep
#include "stdafx.h"
нет
#include
n==0
long int funstep(int x,int n)
{ if (n==0) return 1;
Базисное
утверждение

funstep= x*funstep(x,n-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=1

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

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

Вычисление n - го числа Фибоначчи
fib(n)
// Ex9_2.cpp
Заголовок
нет
#include "stdafx.h"
n=1 или n=2
#include
int fib(int n)
{if((n==1)||(n==2)) return 1; fib=fib(n-1)+fib(n-2)
Базисное утверждение

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=1

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

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

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

18

6
6

Фрейм активации

12

12
6

Фрейм активации

6

12
18

Фрейм активации

r

8

Вычисление наибольшего общего делителя (4)
// Ex9_3.cpp .
#include "stdafx.h"
Базисное
#include
утверждение
int nod(int 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;
}
9

Вычисление наибольшего общего делителя(3)

a
b

18
12

r
6

@r
6
6
@r
12
6
@r
12
18

Фрейм активации
Фрейм активации
Фрейм активации

10

Вычисление наибольшего общего делителя (2)
Заголовок процедуры с
// Ex9_4.cpp
параметром переменной
#include "stdafx.h"
(ссылка)
#include
void nod(int 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;
11
}

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

12

Переворот строки
1) последовательное отсечение начального элемента и добавление
его в конец результирующей строки: (Ex9_5)
S=‘ABC’
S=‘ABC’

Result:=…+S[1]

S=‘BC’

Result:=…+S[1]
S=‘С’

Result:=… +S[1]
S=‘’

Result:=‘’

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

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.

13

Переворот строки
2) последовательная перестановка элементов(Ex9_6),
например
ABCDE ? EBCDA ? EDCBA

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

void reverse (char * s,int n)
{char temp;
Рекурсивная часть
if (n
Определение корней уравнения на заданном отрезке
Базисное утверждение: Если
абсолютная величина
функции в середине
отрезка не превышает
заданного значения
погрешности, то
координата середины
отрезка и есть корень.
Рекурсивное утверждение:
Корень расположен между
серединой отрезка и тем
концом, значение функции
в котором по знаку не
совпадает со значением
функции в середине
отрезка.
15

Определение корней уравнения на заданном отрезке (2)
Если корней на заданном отрезке
нет, то произойдет зацикливание!

// Ex9_7.cpp
#include "stdafx.h"
Заголовок рекурсивной
#include
процедуры
#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);
fabs(f)
Определение корней уравнения на заданном отрезке (2)
// Основная программа

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

int main(int 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.

Return
18

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

Основная программа
Первая активация

i=0
i=1

Вторая активация
i=2

Операторы
"до вызова"

Третья активация - базис

Операторы
"после вызова"

19

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

// Ex9_8.cpp
#include "stdafx.h"
#include
// рекурсивная подпрограмма
void print(int x[],int i)
{if (x[i]==0) puts("***********");
else
{if (x[i]>0)printf("%4d\n",x[i]);
print(x,i+1);
if (x[i]
Просмотр массива (2)
// основная программа
int main(int argc, char* argv[])
{int i,x[40];
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;
}
21

9.3 Древовидная рекурсия. Перестановки
1,2,3 ? 123,132, 213, 231, 312, 321.
Схема формирования перестановок:

22

Перестановки (2)

// Ex9_9.cpp
Заголовок
рекурсивнойподрограммы
#include "stdafx.h"
#include
void perest(int n,int m,const int r[],int pole[])
{int r1[3],k,i,j;
if (n==m){
for(i=0;i
Перестановки (3)
for(j=0;j
9.4 Полный и ограниченный перебор
Пример. Расставить N ферзей на доске N*N так, чтобы они не били
друг друга.

Pole

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

Дерево формирования вариантов

26

Схема алгоритма расстановки ферзей

27

Программа расстановки ферзей
// Ex9_10.cpp
Заголовок функции
#include "stdafx.h"
проверки варианта
#include
#include
// Функция проверки корректности варианта
int new_r(int n,int pole[])
Условие «один ферзь
{int r=1;
бьет другого»
for(int j=0;j
Программа расстановки ферзей (2)
// Процедура расстановки ферзей

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

void ferz(int n,int m,int pole[])
{ int i;
Базисное
if (n==m){
утверждение
for(i=0;i
Программа расстановки ферзей (3)
int main(int argc, char* argv[])
{int pole[10],m;
puts("Input N"); scanf("%d",&m);
ferz(0,m,pole);
Вызов рекурсивной
подпрограммы
return 0;}
Размер доски

Всего
вариантов

Количество
вызовов проц.

Количество
решений

4

256

17

2

5

3125

54

10

6

46656

153

4

7

823543

552

40

8

16777216

2057

92

30






Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.