Рекурсивни функции в математиката

Рекурсия

1. 
   Рекурсивни функции в математиката
   

Ако в дефиницията на някаква функция се използва самата функция, дефиницията на функцията е рекурсивна.

а
) Ако n е произволно естествено число, следната дефиниция на функцията факториел

е рекурсивна. Условието при n = 0 не съдържа обръщение към функцията факториел и се нарича гранично.


б) Функцията за намиране на най-голям общ делител на две естествени числа a и b може да се дефинира по следния рекурсивен начин:
Тук граничното условие е условието при a = b.

в) Ако x е реално, а n – цяло число, функцията за степенуване може да се дефинира рекурсивно по следния начин:

В този случай граничното условие е условието при n = 0.

г) Редицата от числата на Фибоначи

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

м
оже да се дефинира рекурсивно по следния начин:
В този случай имаме две гранични условия – при n = 0 и при n = 1.
Рекурсивната дефиниция на функция може да се използва за намиране стойността на функцията за даден допустим аргумент.

Примери:

а) Като се използва рекурсивната дефиниция на функцията факториел може да се намери факториелът на 4. Процесът за намирането му преминава през разширение, при което операцията умножение с отлага, до достигане на граничното условие 0! = 1. Следва свиване, при което се изпълняват отложените операции.

4! =

4.3! =

4.3.2.1! =

4.3.2.1.0! =

4.3.2.1.1 =

4.3.2.1 =

4.3.2 =

24

б) Като се използва рекурсивната дефиниция на функцията gcd, може да се намери gcd(35, 14).

gcd(21, 14) =

gcd(7, 14) =

gcd(7, 7) =

7.

В този случай няма разширяване, нито пък свиване. Двата аргумента на gcd играят ролята на натрупващи параметри. Те се променят докато се достигне граничното условие.

f
ib(5) = 5

+

fib(4) = 3 fib(3) = 2

+ + + 1

+ 1 1 0 1 0

fib(1) fib(0)

1 0
В този случай намирането на fib(5) генерира дървовиден процес. Операцията + се отлага. Забелязваме много повтарящи се изчисления, например fib(0) се пресмята 3 пъти, fib(1) – 5 пъти, fib(2) - 3 пъти, fib(3) – 2 пъти, което илюстрира неефективността на този вид пресмятане.

2. 
   Рекурсивни функции в C++
   

Известно е, че в тялото на всяка функция може да бъде извикана друга функция, която е дефинирана или е декларирана до момента на извикването й. Освен това, в C++ е вграден т. нар. механизъм на рекурсия – разрешено е функция да вика в тялото си самата себе си.

Функция, която се обръща пряко или косвено към себе си, се нарича рекурсивна. Програма, съдържаща рекурсивна функция е рекурсивна.

Чрез пример ще илюстрираме описанието, обръщението и изпълнението на рекурсивна функция.

Програма Zad85.cpp решава задачата.

#include

int fact(int);

int main()

{cout << "m= ";

int m;

if(!cin || m < 0)

{cout << “Error! \n”;

return 1;

}

cout << m << "!= " << fact(m) << '\n';

}

int fact(int n)

else return n * fact(n-1);

}
В тази програма е описана рекурсивната функция fact, която приложена към естествено число, връща факториела на това число. Стойността на функцията се определя посредством обръщение към самата функция в оператора return n * fact(n-1);.
Изпълнение на програмата

Изпълнението започва с изпълнение на главната функция. Фрагментът

cout << "m= ";

int m;

въвежда стойност на променливата m. Нека за стойност на m е въведено 4. В резултат в стековата рамка на main, отделените 4B за променливата m се инициализират с 4. След това се изпълнява операторът

cout << m << "!= " << fact(m) << '\n';

За целта трябва да се пресметне стойността на функцията fact(m) за m равно на 4, след което получената стойност да се изведе. Обръщението към функцията fact е илюстрирано по-долу:

Генерира се стекова рамка за това обръщение към функцията fact. В нея се отделят 4B ОП за фактическия параметър n, в която памет се откопирва стойността на фактическия параметър m и започва изпълнението на тялото на функцията. Тъй като n е различно от 0, изпълнява се операторът

return n * fact(n-1);

при което трябва да се намери fact(n-1), т.е. fact(3). По такъв начин преди завършването на първото обръщение към fact се прави второ обръщение към тази функция. За целта се генерира нова стекова рамка на функцията fact, в която за формалния параметър n се откопирва стойност 3. Тялото на функцията fact започва да се изпълнява за втори път (Временно спира изпълнението на тялото на функцията, предизвикано от първото обръщение към нея).

По аналогичен начин възникват още обръщения към функцията fact. При последното от тях, стойността на формалния параметър n е равна на 0 и тялото на fact се изпълнява напълно. Така се получава:

n 4 0x0066FDA0

стекова рамка на 1-во

обръщение към fact

n 0x0066FD48 стекова рамка на 2-ро

n 0x0066FCF0

стекова рамка на 3-то

обръщение към fact

n 0x0066FC98

стекова рамка на 4-ро

обръщение към fact

n 0x0066FC40

стекова рамка на 5-то

обръщение към fact

При петото обръщение към fact стойността на n е равна на 0. В резултат, изпълнението на това обръщение завършва и за стойност на fact се получава 1. След това последователно завършват изпълненията на останалите обръщения към тялото на функцията. При всяко изпълнение на тялото на функцията се определя съответната стойност на функцията fact. След завършването на всяко изпълнение на функцията fact, отделената за fact стекова рамка се освобождава. В крайна сметка в главната програма се връща 24 - стойността на 4!, която се извежда върху екрана.

В този случай, рекурсивното дефиниране на функцията факториел не е подходящо, тъй като съществува лесно итеративно решение.

Съществуват обаче задачи, които се решават трудно ако не се използува рекурсия.

(<формула><знак><формула>)

Програмата да намира и извежда стойността на въведената формула (Например 8 --> 8; ((2-6)*4) --> -16).

#include

int formula();

int main()

{cout << formula() << "\n";

return 0;

}

int formula()

int x, y;

cin >> c; // c е ‘(‘ или цифра

// <формула> ::= <цифра>

if (c >= '0' && c <= '9') return (int)c – (int)'0';

else

{x = formula();

cin >> op;

y = formula();

cin >> c; // прескачане на ‘)’

switch (op)

{case '+': return x + y; break;

case '-': return x - y; break;

case '*': return x * y; break;

default: cout << "error\n"; return 111;

}

}

}

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

Програма Zad87.cpp решава задачата.

Program Zad87.cpp

#include

int gcd(int, int);

int main()

{cout << "a, b= ";

int a, b;

cin >> a >> b;

if (!cin || a < 1 || b < 1)

{cout << "Error! \n";

return 1;

}

cout << "gcd{" << a << ", " << b << "}= " << gcd(a, b) << "\n";

}

int gcd(int a, int b)

if(a > b) return gcd(a-b, b);

else return gcd(a, b-a);

}
Задача 88. Като се използва рекурсивната дефиниция на функцията за степенуване да се напише програма, която по дадени a реално и k – цяло число, намира стойността на a^k.

#include

double pow(double, int);

int main()

{cout << "a= ";

double a;

cin >> a;

if (!cin)

{cout << "Error \n";

return 1;

}

cout << "k= ";

cin >> k;

if (!cin)

{cout << "Error \n";

return 1;

}

cout << "pow{" << a << ", " << k << "}= " << pow(a, k) << "\n";

}

double pow(double x, int n)

if (n > 0) return x * pow(x, n-1);

else return 1.0/pow(x, -n);

}
Задача 89. Квадратна мрежа с k реда и k стълба (1 ≤ k ≤ 20) има два вида квадратчета - бели и черни. В черно квадратче може да се влезе, но не може да се излезе. От бяло квадратче може да се премине във всяко от осемте му съседни, като се прекоси общата им страна или връх. Да се напише програма, която ако са дадени произволна мрежа с бели и черни квадратчета и две произволни квадратчета - начално и крайно, определя дали от началното квадратче може да се премине в крайното.

а) Ако началното квадратче не е в мрежата, приемаме, че не може да се премине от началното до крайното квадратче.

б) Ако началното квадратче съвпада с крайното, приемаме, че може да се премине от началното до крайното квадратче.

в) Ако началното и крайното квадратчета са различни и началното квадратче е черно, не може да се премине от него до крайното квадратче.

г) Във всички останали случаи, от началното квадратче може да се премине до крайното тогава и само тогава, когато от някое от съседните му квадратчета (в хоризонтално, във вертикално или диагонално направление), може да се премине до крайното квадратче.
Програма Zad89.cpp решава задачата.

Представяне на данните:

Мрежата ще представим чрез квадратна матрица от цели числа mr[k x k] (1 ≤ k ≤ 20) и ще реализираме чрез съответен двумерен масив. При това mr[i][j] е равно на 0, ако квадратче (i, j) е бяло и е равно на 1, ако е квадратче (i, j) е черно (0 ≤ i ≤ k-1, 0 ≤ j ≤ k-1). Нека началното квадратче е от ред x и стълб y, а крайното квадратче е от ред m и стълб n.

В програмата Zad89.cpp е дефинирана рекурсивната функция way. Тя връща стойност true, ако от квадратче (x, y) може да се премине до квадратче (m, n) и false - в противен случай. За да се избегне зацикляне (връщане в началното квадратче от всяко съседно), се налага преди рекурсивните обръщения към way, да се промени стойността на mr[x][y] като квадратчето (x, y) се направи черно.
Program Zad89.cpp

#include

int mr[20][20];

int k, m, n;

bool way(int, int);

void writemr(int, int [][20]);

int main()

{cout << "k from [1, 20] = ";

do

{cin >> k;

int x, y;

do

{cout << "x, y = ";

} while (x < 0 || x > k-1 || y < 0 || y > k-1);

do

{cout << "m, n = ";

} while (m < 0 || m > k-1 || n < 0 || n > k-1);

for (int i = 0; i <= k-1; i++)

for (int j = 0; j <= k-1; j++)

cin >> mr[i][j];

cout << "\n";

writemr(k, mr);

if (way(x, y)) cout << "yes \n";

else cout << "no \n";

return 0;

}

bool way(int x, int y)

if (x == m && y == n) return true; else

if (mr[x][y] == 1) return false; else

{mr[x][y] = 1;

bool b = way(x+1, y) || way(x-1, y) ||

way(x, y+1) || way(x, y-1) ||

way(x-1,y-1) || way(x-1, y+1)||

way(x+1,y-1) || way(x+1, y+1);

mr[x][y] = 0;

return b;

}

}

void writemr(int k, int mr[][20])

{for (int j = 0; j <= k-1; j++)

cout << mr[i][j];

cout << '\n';

}

}
Задача 90. Да се напише рекурсивен вариант на функцията от по-висок ред accumulate.

typedef double (*type1) (double, double);

typedef double (*type2) (double);
double accumulate(type1 op, double null_val, double a, double b,

type2 f, type2 next)

{if (a > b + 1e-14) return null_val;

else return op(f(a),

accumulate(op, null_val, next(a), b, f, next));

}

Задача 91. Да се напише рекурсивна функция double min(int n, double* x), която намира минималния елемент на редицата x₀, x₁, ..., x_n-1.

double min(int n, double* x)

{double b;

if (n == 1) return x[0]; else

{b = min(n-1, x);

if (b < x[n-1]) return b; else return x[n-1];

}

}
второ решение:

{double b;

if (n == 1) return x[0]; else

{b = min(n-1, x+1);

if (b < x[0]) return b; else return x[0];

}

}

bool member(int x, int n, int* a)

{if (n == 1 ) return a[0] == x;

return x == a[0] || member(x, n-1, a+1);

}
второ решение:

bool member(int x, int n, int* a)

{if (n == 1 ) return a[0] == x;

return x == a[n-1] || member(x, n-1, a);

}
Задача 93. Да се напише рекурсивна функция, която проверява дали редицата x₀, x₁, ..., x_n-1 е монотонно растяща.
първо решение:

bool monincr(int n, double* x)

{if (n == 1) return true; else

return x[n-2] <= x[n-1] && monincr(n-1, x);

}

второ решение:

bool monincr(int n, double* x)

{if (n == 1) return true; else

return x[0] <= x[1] && monincr(n-1, x+1);

}

Задача 94. Да се напише рекурсивна функция, която проверява дали редицата a₀, a₁, ..., a_n-1 се състои от различни елементи.
първо решение:

bool differ(int n, int* a)

{if (n == 1) return true; else

return !member(a[0], n-1, a+1) && differ(n-1, a+1);

}
второ решение:

bool differ(int n, int* a)

{if (n == 1) return true; else

return !member(a[n-1], n-1, a) && differ(n-1, a);

}
Задача 95. Дадена е квадратна мрежа от клетки, всяка от които е празна или запълнена. Запълнените клетки, които са свързани, т.е. имат съседни в хоризонтално, вертикално или диагонално направление, образуват област. Да се напише програма, която намира броя на областите и размера (в брой клетки) на всяка област.

Програма Zad95.cpp решава задачата.

Мрежата ще представим чрез квадратна матрица от цели числа mr[n x n] (1 ≤ n ≤ 20) и ще реализираме чрез съответен двумерен масив. При това mr[i][i] е 1 ако квадратче (i, j) е запълнено и 0 – в противен случай (0 ≤ i ≤ n-1, 0 ≤ j ≤ n-1).

Ще дефинираме функция broy, която преброява клетките в областта, съдържаща дадена клетка (x, y). Функцията има два параметъра x и y - координатите на точката и реализира следния алгоритъм:

а) Ако клетката с координати (x, y) е извън мрежата, приемаме, че броят на клетките в областта е равен на 0.

б) В противен случай, ако клетката с координати (x, y) е празна, приемаме, че броят е равен на 0.

в) В останалите случаи, броят на клетките в областта е равен на сумата от 1 и броя на клетките на всяка област, на която принадлежат осемте съседни клетки на клетката (x, y).

От подточка в) следва, че функцията broy е рекурсивна. За да избегнем зацикляне и многократно преброяване, трябва преди рекурсивното обръщение на направим клетката (x, y) празна.

#include

int mr[20][20];

int n;

{if (x < 0 || x > n-1 || y < 0 || y > n-1) return 0;

else if (mr[x][y] == 0) return 0;

else {mr[x][y] = 0;

return 1 + broy(x-1, y+1) + broy(x, y+1)

+ broy(x+1, y+1) + broy(x+1,y)

+ broy(x+1, y-1) + broy(x, y-1)

+ broy(x-1, y-1) + broy(x-1, y);

}

}

int main()

do

{cout << "n= ";

}while (n < 1 && n > 20);

for (int i = 0; i <= n-1; i++)

for (int j = 0; j <= n-1; j++)

cin >> mr[i][j];

int br = 0;

for (i = 0; i <= n-1; i++)

for (int j = 0; j <= n-1; j++)

if (mr[i][j] == 1)

{br++;

}

return 0;

Ще дефинираме рекурсивната булева функция way, която зависи от два параметъра i и j, показващи номерата на градовете, между които се търси дали съществува път. Функцията реализира следния алгоритъм:

а) Ако i = j, съществува път от град i до град j.

б) Ако i ≠ j и има пряк път от град i до град j, има път между двата града.

в) В останалите случаи има път от град i до град j, тогава и само тогава, когато съществува град k, с който град i е свързан с пряк път и от който до град j има път.

Програма Zad96.cpp решава задачата.

#include

int arr[10][10];

int n;

{if (i == j) return true; else

if (arr[i][j] == 1) return true; else

{bool b = false;

int k = -1;

do

{k++;

{arr[i][k] = 0; arr[k][i] = 0;

b = way(k, j);

arr[i][k] = 1; arr[k][i] = 1;

}

}while (!b && k <= n-2);

}

}

{do

cin >> n;

}while (n < 1 || n > 10);

for (int i = 0; i <= n-1; i++)

for (int j = 0; j <= n-1; j++)

arr[i][j] = 0;

for (i = 0; i <= n-2; i++)

for (int j = i+1; j <= n-1; j++)

{cout << "connection between " << i

<< " and " << j << " 0/1? ";

cin >> arr[i][j];

arr[j][i] = arr[i][j];

}

int j;

{cout << "start and final towns: ";

cin >> i >> j;

}while (i < 0 || i > 9 || j < 0 || j > 9);

if (way (i, j)) cout << "yes \n";

else cout << "no\n";

return 0;

}

Задача 97. Дадени са n града (n е естествено число, 1 ≤ n ≤ 10) и целочислена матрица Anxn, така че a_ij е равно на 1, ако има пряк път от град i до град j и е 0 в противен случай (0 ≤ i, j ≤ n-1). Да се напише програма, която намира пътя между два произволно зададени града в случай, че път между тях съществува.

Процедурата foundway намира пътя от град i до град j в случай, че съществува, т.е. ако way(i, j) има стойност true. Пътят се записва в едномерния масив int x[100]. Дължината на пътя се записва в променливата s.

Програма Zad97.cpp решава задачата. В нея е пропусната дефиницията на функцията way. При обръщение към функцията foundway параметърът-псевдоним s трябва да се свърже с параметър, инициализиран с –1.
Program Zad97.cpp

#include

int arr[10][10];

int n;
bool way(int i, int j)

...

void foundway(int i, int j, int& s, int x[])

x[s] = i;

if (i != j)

if (arr[i][j] == 1)

{s++;

x[s] = j;

else

int k = -1;

do

{k++;

}while (!b);

arr[i][k] = 0; arr[k][i] = 0;

foundway(k, j, s, x);

arr[i][k] = 1; arr[k][i] = 1;

}

}

{int p = -1;

int a[100];

do

{cout << "n= ";

}while (n < 1 || n > 10);

for (int i = 0; i <= n-1; i++)

for (int j = 0; j <= n-1; j++)

arr[i][j] = 0;

for (i = 0; i <= n-2; i++)

for (int j = i+1; j <= n-1; j++)

{cout << "connection between " << i << " and "

cin >> arr[i][j];

arr[j][i] = arr[i][j];

}

int j;

{cout << "start and final towns: ";

cin >> i >> j;

}while (i < 0 || i > 9 || j < 0 || j > 9);

if(way (i, j))

{foundway(i, j, p, a);

p++;

for (int l = 0; l <= p-1; l++) cout << a[l] << " " ;

}

else cout << "no\n";

}

Задача 98. Дадени са n града (n е естествено число, 1 ≤ n ≤ 10) и целочислена матрица Anxn, така че a_ij е равно на 1, ако има пряк път от град i до град j и е 0 в противен случай (0 ≤ i, j ≤ n-1). Да се напише булева функция fixway(int i, int j, int p), която установява дали съществува път с дължина p от град i до град j (p ≥ 1).

Булевата функция fixway реализира следния алгоритъм:

а) Ако p = 1, има път от град i до град j с дължина p ако има пряк път между двата града.

б) Ако p > 1, има път от град i до град j с дължина p тогава и само тогава, когато съществува град k, с който град i е свързан с пряк път и от който до град j има път с дължина p-1.

Следващият програмен фрагмент дефинира само функцията fixway.
bool fixway(int i, int j, int p)

{if (p == 1) return arr[i][j] == 1; else

{bool b = false;

int k = -1;

do

{k++;

}while (!b && k <= n-2);

return b;

}

}

Ако търсим съществуването само на ациклични пътища, ще използваме модификацията на горната функция, дадена по-долу.

{bool b;

if (p == 1) return arr[i][j] == 1; else

{b = false;

k = -1;

{k++;

{arr[i][k] = 0; arr[k][i] = 0;

b = fixway(k, j, p-1);

arr[i][k] = 1; arr[k][i] = 1;

}

}while (!b && k <= n-2);

}

}

#include

int arr[10][10];

int n;
bool fixway(int i, int j, int p)

...

void foundfixway(int i, int j, int p, int& s, int* x)

x[s] = i;

if(p == 1)

{s++;

}

else

int k = -1;

do

{k++;

}while (!b);

foundfixway(k, j, p-1, s, x);

}

}

{int p = -1;

int a[100];

do

{cout << "n= ";

}while (n < 1 || n > 10);

for (int i = 0; i <= n-1; i++)

for (int j = 0; j <= n-1; j++)

arr[i][j] = 0;

for (i = 0; i <= n-2; i++)

for (int j = i+1; j <= n-1; j++)

{cout << "connection between " << i << " and "

cin >> arr[i][j];

arr[j][i] = arr[i][j];

}

int j, l;

{cout << "start and final towns, and len between them: ";

cin >> i >> j >> l;

}while (i < 0 || i > 9 || j < 0 || j > 9);

if (fixway (i, j, l))

{foundfixway(i, j, l, p, a);

for (int m = 0; m <= l; m++) cout << a[m] << " " ;

cout << endl;

}

else cout << "no\n";

}

Ack(0, n) = n+1

Ack(m, 0) = Ack(m-1, 1), m > 0

Ack(m, n) = Ack(m-1, Ack(m, n-1)), m > 0, n > 0.

където x и a_i (0 ≤ i ≤ n) са дадени реални числа.

а) броят на квадратчетата от областта, в която се съдържа даденото квадратче.

б) броят на областите с цвят, съвпадащ с цвета на даденото квадратче.

в) броят на областите с цвят, различен от цвета на даденото квадратче.

г) броят на квадратчетата с цвят, съвпадащ с цвета на даденото квадратче, които не са в една област с него.

Задача 11. Дадено е множество от n града и за всеки два от тях е определено дали са свързани с път или не. Едно множество от градове ще наричаме пълно, ако всеки два различни града, принадлежащи на множеството, са свързани с път. Да се напише програма, която по дадено k, k < n, извежда всички пълни множества, състоящи се от k на брой града.

Задача 12. Дадено е множество от n града и за всеки два от тях е определено дали са свързани с път или не. Едно множество от градове ще наричаме независимо, ако всеки два различни града, принадлежащи на множеството, не са свързани с път. Да се напише програма, която по дадено k, k < n, извежда всички независими множества, състоящи се от k на брой града.

Задача 13. Да се напише програма, която намира стойността на произволен израз от вида

израз ::= цяло_число |

(израз * израз).

Задача 14. Да се напише програма, която намира стойността на произволен израз от вида

израз ::= цяло_число |

(израз ^ израз),

където с ^ е означена операцията степенуване.

<операция>(<операнди>)

<операнд>, <операнди>

където not има само един операнд, а and и or могат да имат произволен брой операнди. Програмата намира и извежда стойността на булевия израз.

1. 
   Ст. Липман, Езикът C++ в примери, “КОЛХИДА ТРЕЙД” КООП, С. 1993.
   
2. 
   М. Тодорова, Програмиране на Паскал, Полипринт Враца, С., 1993.
   
3. 
   М. Тодорова, Езици за функционално и логическо програмиране – функционално програмиране, СОФТЕХ, С., 1998.