Structural Programming

Auditory Exercise 10 - Recursion

1. Recursive Functions

Functions in C++ programming language can call other functions. This calling can continue to an arbitrary depth.

If a function calls itself, it is called recursive call, and this method of calling is known as recursion.

Example of a recursive function:

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

1.1. Task 1

To calculate the sum 1! + (1+2)! + (1+2+3)! + … + (1+2+…+n)!, follow these steps: - use a recursive function to calculate the sum of the first k natural numbers. - use a recursive function to calculate the factorial of a natural number.

#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. Task 2

Write a recursive function count_down(int n) that for a given integer n prints the numbers from n to 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 Task 2.1

Write a recursive function count_up(int n) that for a given integer n prints the numbers from 0 to n. (Use the code of the function count_down(int n) and solve the task by changing the order of the commands).

#include <iostream>
using namespace std;

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

1.3. Task 3

Write a program that for a given natural number, calculates the difference between the nearest larger prime number and the number itself.

The program should use a recursive function to find the appropriate prime number, which in turn should use a recursive function to check if a given number is a prime number.

Example:

If 573 is entered, the program should print 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. Task 4

Write a program that will print the value of the n-th element of the array defined by:

    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. Task 5

Write a recursive function that will calculate the sum of the digits of a number.

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. Task 6

For a given number n, write a recursive function that will count the occurrences of the digit 8. Additionally, if there is another digit 8 immediately to the left of any 8, its occurrence should be counted twice.

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. Task 7

Write a program that for a given array of natural numbers (input from the keyboard), will print the greatest common divisor (GCD) of its elements. The program must include a recursive function for calculating the GCD of two natural numbers.

Example

48 36 120 72 84

The output should be:

GCD of the elements in this array is 12

• The GCD for two numbers can be calculated using the Euclidean algorithm
• To calculate the GCD of numbers m and n, the remainder is calculated when dividing m by n.
  • If the reminder is not 0, calculate the remainder when dividing n by m % n
  • Repeat the process until non-zero remainders are obtained
  • If the reminder is 0, the GCD of the two numbers is the last calculated non-zero remainder

Example

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

GCD(20, 12) = 4

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


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

int main() {
    int i, n, a[MAX];
    
    cout << "Size of the array: ";
    cin >> n;

    cout << "Elements of the array: \n";
    for (i = 0; i < n; ++i) {
        cin >> a[i];
    }

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

    cout << "GCD of the elements in this array is " << gcd;
    return 0;
}

1.8. Task 8 (Homework)

Write a program that for a given array of integers (input from the keyboard), will print the least common multiple (LCM) of its elements. The program must include a recursive function for calculating the LCM of two numbers.

Example: For the array 18 12 24 36 6 the output should be:

LCM of the elements in this array is 72

1.9. Task 9

Write a program that for a given array of integers (input from the keyboard) will print the sum of elements from the array. The program should include a recursive function for finding the sum of elements in a given array.

#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. Task 10 (Homework)

Write a program that for a given array of integers (input from the keyboard), will print the largest element. The program should include a recursive function for finding the largest element in a given array.

Example: For the array

5 8 3 12 9 6 

The output should be:

The largest element in the array should be 12