Структурно програмирање

Аудиториска вежба 10 - Рекурзија

1. Рекурзивни функции

Функциите во програмскиот јазик Ц++ може да повикуваат други функции. Ова повикување може да оди во произволна длабочина.

Доколку една функција се повикува сама себе, тогаш тоа се нарекува рекурзивен повик, односно тој начин на повикување се нарекува рекурзија.

Пример за рекурзивна функција:

    int factoriel(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factoriel(n-1);
    }

1.1. Задача 1

Да се пресмета збирот 1! + (1+2)! + (1+2+3)! + … + (1+2+…+n)! притоа: - користете рекурзивна функција за пресметување на збирот на првите k природни броеви. - користете рекурзивна функција за пресметување на факториел на еден природен број.

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

int sum(int k) {
    if (k == 0)
        return 0;
    else
        return k + sum(k - 1);
}

int main() {
    int i, n, result = 0;
    cin >> n;

    if (n > 0) {
        for (i = 1; i < n; i++) {
            int s = sum(i);
            result += factorial(s);
            cout << s << "! + ";
        }

        int s = sum(n);
        result += factorial(s);
        cout << s << "! = " << result << endl;
    } else {
        cout << "Wrong input" << endl;
    }

    return 0;
}

1.2. Задача 2

Да се напише рекурзивна функција count_down(int n) која за даден цел број n ќе овозможи печатење на броевите од n до 0.

#include <iostream>
using namespace std;

void count_down(int n){
    if(n == 0){
        cout<<0<<" ";
        return;
    }
    cout<<n<<" ";
    count_down(n-1);
}

1.2.1 Задача 2.1

Да се напише рекурзивна функција count_up(int n) која за даден цел број n ќе овозможи печатење на броевите од 0 до n. (Искористете го кодот на функцијата count_down(int n) и решете ја задачата со промена на редоследот на командите).

#include <iostream>
using namespace std;

void count_up(int n){
    if(n == 0){
        cout<<0<<" ";
        return;
    }
    count_up(n-1);
    cout<<n<<" ";
}

1.3. Задача 3

Да се напише програма која за даден природен број ја пресметува разликата помеѓу најблискиот поголем од него прост број и самиот тој број.

Програмата треба да користи рекурзивна функција за наоѓање на соодветниот прост број, која пак треба да користи рекурзивна функција за проверка дали даден број е прост број.

Пример:

Ако се внесе 573, програмата треба да испечати 577 - 573 = 4

#include <iostream>
using namespace std;

int is_prime(int n, int i);

int first_larger_prime(int n);

int main() {
    int number, difference;
    cin >> number;

    difference = first_larger_prime(number) - number;

    cout << first_larger_prime(number) << " - " << number << " = " << difference << endl;

    return 0;
}

int is_prime(int n, int i) {
    if (n < 4)
        return 1;
    else if ((n % 2) == 0)
        return 0;
    else if (n % i == 0)
        return 0;
    else if (i * i > n)
        return 1;
    else
        return is_prime(n, i + 2);
}

int first_larger_prime(int n) {
    if (is_prime(n + 1, 3))
        return n + 1;
    else
        return first_larger_prime(n + 1);
}

1.4. Задача 4

Да се напише програма што ќе ја испишува вредноста на n-тиот член на низата дефинирана со:

    x[1] = 1
    x[2] = 2
    ...
    x[n] = (n - 1) * x[n - 1] / n + x[n - 2] / n

#include <iostream>
using namespace std;

float xnn(int n) {
  if (n == 1)
    return 1;
  if (n == 2)
    return 2;
  return (n - 1) * xnn(n - 1) / n + xnn(n - 2) / n;
}

int main() {
  int n;
  cin >> n;
  cout << "xnn(" << n << ") = " <<  xnn(n) << endl;
  return 0;
}

1.5. Задача 5

Да се напише рекурзивна функција која ќе го пресметува збирот на цифрите на еден број.

sumDigits(126) -> 9
sumDigits(49) -> 13
sumDigits(12) -> 3

#include<iostream>
using namespace std;

int sumDigits(int n) {
  if (n == 0) 
    return 0;
  return n % 10 + sumDigits(n / 10);
}

1.6. Задача 6

За даден број n, да се напише рекурзивна функција која ќе ги изброи појавувањата на цифрата 8. Притоа, доколку до некоја цифра 8 има уште една цифра 8 веднаш лево од неа, нејзиното појавување се брои двојно.

count8(8) -> 1
count8(818) -> 2
count8(8818) -> 4

#include <iostream>
using namespace std;

int count8(int n) {
  if (n == 0)
    return 0;
  if ((n / 10) % 10 == 8 && n % 10 == 8)
    return 2 + count8(n / 10);
  if (n % 10 == 8)
    return 1 + count8(n / 10);
  return count8(n / 10);
}

1.7. Задача 7

Да се напише програма која што за дадена низа од природни броеви (која што се внесува од тастатура) ќе го отпечати најголемиот заеднички делител (НЗД) на нејзините елементи. Програмата задолжително треба да содржи рекурзивна функција за пресметување НЗД на два природни броја.

Пример

48 36 120 72 84

На екран треба да отпечати:

NZD na elementite na ovaa niza e 12

• НЗД за два броја може да се пресмета со користење на Евклидовиот алгоритам
• За да се пресмета НЗД на броевите m и n, се пресметува остатокот при делење на m со n.
  • ако остатокот не е 0, се пресметува остатокот при делење на n со m % n
  • постапката се повторува се додека се добиваат ненулти остатоци
  • ако остатокот е 0, НЗД на двата броја е последниот пресметан ненулти остаток

Пример

NZD(20, 12)
20 % 12 = 8
12 % 8 = 4
8 % 4 = 0

NZD(20, 12) = 4

#include <iostream>
using namespace std;
#define MAX 100


int NZD(int m, int n) {
    if (!n) {
        return m;
    }
    return NZD(n, m % n);
}

int main() {
    int i, n, a[MAX];
    
    cout << "Vnesi ja goleminata na nizata: ";
    cin >> n;

    cout << "Vnesi gi elementite na nizata: \n";
    for (i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int nzd = NZD(a[0], a[1]);
    for (i = 2; i < n; ++i) {
        nzd = NZD(nzd, a[i]);
    }

    cout << "NZD na elementite od nizata e " << nzd;
    return 0;
}

1.8. Задача 8 (За Дома)

Да се напише програма која за дадена низа од цели броеви (која се внесува од тастатура), ќе го отпечати најмалиот заеднички содржател (НЗС) на нејзините елементи. Програмата треба задолжително да содржи рекурзивна функција за пресметување НЗС на два броја.

Пример: За низата 18 12 24 36 6 на екран треба да се отпечати:

NZS na elementite na ovaa niza e 72

1.9. Задача 9

Да се напише програма која за дадена низа од цели броеви (која што се внесува од тастатура) ќе го отпечати збирот на елементи од низата. Програмата треба да содржи рекурзивна функција за наоѓање на збирот на елементите во дадена низа.

#include <iostream>
using namespace std;

int sum_elements(int array[], int n);

int main() {
    int i, n, a[100];

    cin >> n;

    for (i = 0; i < n; i++)
        cin >> a[i];

    cout << "The sum of all of the array elements is: " << sum_elements(a, n - 1) << endl;

    return 0;
}

int sum_elements(int array[], int n) {
    if (n == 0) {
        return array[n];
    } else {
        return array[n] + sum_elements(array, n - 1);
    }
}

1.10. Задача 10 (За Дома)

Да се напише програма која за дадена низа од цели броеви (која што се внесува од тастатура) ќе го отпечати најголемиот елемент. Програмата треба да содржи рекурзивна функција за наоѓање на најголем елемент во дадена низа.

Пример: За низата

5 8 3 12 9 6 

На екран треба да се отпечати:

Najgolem element vo nizata e 12