Приклади розвʼязку задач на рекурсію

---

Зміст

• 1. Обчислення площі трикутника
• 2. Обчислити значення квадрата числа на основі залежності
• 3. Комбінаторна задача
• 4. Синтаксичний аналізатор для поняття “ідентифікатор”
• 5. Значення функції Аккермана
• 6. Синтаксичний аналізатор для поняття “простий вираз”
• 7. Синтаксичний аналізатор для поняття “сума”
• 8. Перевід з однієї системи числення в іншу
• 9. Рекурсивна функція Min(). Пошук мінімального значення в масиві типу double[]
• 10. Рекурсивна функція ConvertAnyR(). Перевід числа з однієї системи числення в іншу
• 11. Рекурсивна функція isPrime(). Визначити, чи число є простим
• Зв’язані теми

---

Пошук на інших ресурсах:

1. Обчислення площі трикутника

Задача. Задано трикутник розміром m×n, де m, n – цілі числа і m>0, n>0. Розробити рекурсивну функцію, яка обчислює площу трикутника на основі залежності:

Розв’язок. Якщо відома залежність, то реалізація функції не представляє особливих проблем. Припинення рекурсивного процесу буде здійснюватись при виконанні умови n=m=1.

Програмний код функції S() наступний:

static int S(int n, int m) {
    if ((n==1)&&(m==1)) return 1;
    else
        if (n>1)
            return S(n-1,m)+m;
        else
            return S(n,m-1)+1;
}

  ⇑

2. Обчислити значення квадрата числа на основі залежності

Задача. Обчислити значення квадрата цілого додатного числа n, якщо відома залежність

n² = (n-1)² + 2·(n-1) + 1

З цієї залежності виникає формула рекурсії:

Розв’язок.

// обчислення квадрату числа
static int f(int n) {
    if (n==1)
        return 1;
    else
        return f(n-1)+2*n-1;
}

  ⇑

3. Комбінаторна задача

Задача. Обчислити кількість комбінацій з n різних елементів по m. Кількість комбінацій визначається формулою

Розв’язок.

// кількість комбінацій з n по m
static int C(int n, int m) {
    if ((m==0)&&(n>0) || (m==n)&&(n>0))
        return 1;
    else
        if ((m>n)&&(n>=0))
            return 0;
        else
            return C(n-1,m-1) + C(n-1,m);
}

  ⇑

4. Синтаксичний аналізатор для поняття “ідентифікатор”

Задача. Розробити рекурсивну функцію, яка реалізує синтаксичний аналізатор для поняття ідентифікатор. Як відомо, у мові програмування Java ідентифікатор підпорядковується таким правилам:

• першим символом ідентифікатора обовʼязково є літера латинського алфавіту;
• другий, третій і т.д. символ ідентифікатора може бути літерою або цифрою.

Загальна формула ідентифікатора наступна:

де

• identifier – деякий ідентифікатор;
• letter – деяка літера латинського алфавіту (від ‘a’ до ‘z’ або від ‘A’ до ‘Z’);
• digit – цифра від ‘0’ до ‘9’.

Розв’язок. У даному випадку реалізується рекурсивна функція з іменем IsIdentifier(). Оскільки, функція аналізує поняття “іденитфікатор”, то результатом повернення з функції є значення типу boolean. Якщо функція повертає true, то ім’я ідентифікатора згідно з умовою задачі вірне. Якщо функція повертає false, то в імені ідентифікатора є помилка.

Вхідним параметром рекурсивної функції IsIdentifier() є рядок типу String. Цей рядок містить назву ідентифікатора. Перегляд ідентифікатора здійснюється з кінця до початку. Умовою закінчення рекурсивного процесу є досягнення першого символу ідентифікатора.

Текст методу IsIdentifier() наступний

// визначення, чи рядок s є ідентифікатором
static boolean IsIdentifier(String s, int pos) {
    char c;
    if (pos==0) {
        c = s.charAt(pos); // взяти символ в позиції pos
        if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z'))
            return IsIdentifier(s,pos+1);
        else
            return false;
    }
    else
        if (pos<s.length()) {
            c = s.charAt(pos); // взяти символ
            if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z') || (c>='0')&&(c<='9'))
                return IsIdentifier(s, pos+1);
            else
                return false;
        }
        else
            return true;
}

Використання методу в іншому програмному коді

boolean b;
String s = "Alkjlkjlkj445l25k3j1";
b = IsIdentifier(s,0); // b = true

  ⇑

5. Значення функції Аккермана

Задача. Обчислити значення функції Аккермана для двох невідʼємних цілих чисел n та m, де:

Розв’язок. Якщо відомі залежності, то реалізація функції не є важкою. Згідно з умовою задачі функція отримує два параметри. Це є невід’ємні цілі числа n та m. Повертає функція також ціле невід’ємне число.

При великих значеннях n та m може виникнути переповнення стеку, тому що функція Аккермана є двічі рекурсивною: один з аргументів функції є таж рекурсивна функція.

Реалізація функції наступна:

static int A(int n, int m) {
    if (n==0)
        return m+1;
    else
        if ((n!=0)&&(m==0))
            return A(n-1,1);
        else
            return A(n-1,A(n,m-1));
}

Використання функції в іншому методі

int res;
res = A(1,2); // res = 4
res = A(0,1); // res = 2
res = A(0,0); // res = 1
res = A(2,2); // res = 7
res = A(3,2); // res = 29
res = A(3,3); // res = 61

 

  ⇑

6. Синтаксичний аналізатор для поняття “простий вираз”

Задача. Скласти програму, що реалізує синтаксичний аналізатор для поняття “expression”

де

• Expression – деякий простий вираз;
• simple_identifier – деякий простий ідентифікатор;
• letter – буква латинського алфавіту від ‘a’ до ‘z’ або від ‘A’ до ‘Z’;
• operation – знак операції ‘+’, ‘–’ або ‘*’.

Розв’язок. Для розв’язку даної задачі потрібно реалізувати три функції:

• функцію IsIdentifier(), яка визначає чи простий ідентифікатор є літерою;
• функцію IsOperation(), яка визначає чи є операція синтаксично вірною згідно з умовою задачі;
• рекурсивну функцію IsExpression(), яка визначає чи є простий вираз синтаксично правильним згідно з умовою задачі.

Рекурсивна функція IsExpression() отримує 3 параметри:

• рядок s, який обробляється;
• позиція pos поточного символу в рядку s;
• прапорець IsOp, який визначає чи попередній символ був знаком операції.

Реалізація функцій IsIdentifier(), IsOperation() та IsExpression() наступна:

// простий ідентифікатор
static boolean IsIdentifier(char c) {
  // перевірка, чи ідентифікатор є літерою
  if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z'))
    return true;
  else
    return false;
}

// знак операції
static boolean IsOperation(char c) {
  if ((c=='-') || (c=='+') || (c=='*'))
    return true;
  else
    return false;
}

// Рекурсивна функція-аналізатор виразу
static boolean IsExpression(String s, int pos, boolean IsOp) {
  char c;
  c = s.charAt(pos);

  // якщо перший символ
  if (pos==0) {
    if (IsIdentifier(c)) // перевірка, чи перший символ літера
      return IsExpression(s,pos+1,false);
    else
      return false;
  }
  else
    if (pos<s.length()-1) {
      // не перший і не останній символ
      if (IsIdentifier(c)) // якщо ідентифікатор, то перейти далі на наступний символ
        return IsExpression(s,pos+1,false);
      else {
        // після операції слідує простий вираз
        if (IsOperation(c) && (!IsOp))
          return IsExpression(s,pos+1,true); // вказати на наступному рівні, що була операція
        else
          return false;
      }
    }
    else {
      // інакше, обробити останній символ в рядку
      if (IsOperation(c)) // якщо останній символ операція, то вираз помилковий
        return false;
      else
        return IsIdentifier(c); // перевірити, чи останній символ ідентифікатор
    }
}

Демонстрація використання функції IsExpression() в іншому методі:

boolean res;
res = IsExpression("a+b",0,false); // res = true
res = IsExpression("+a+b",0,false); // res = false
res = IsExpression("ABCsdl-Sdl+Dfjls",0,false); // res = true
res = IsExpression("a+-b-c",0,false); // res = false
res = IsExpression("a+b;",0,false); // res = false
res = IsExpression("alsd+bsldk-",0,false); // res = false
res = IsExpression("AbcDEf",0,false); // res = true

За подібним зразком можна створити декілька рекурсивних функцій, які будуть аналізувати складні вирази. Важливо для кожної функції визначити правильні залежності (алгоритм).

 

  ⇑

7. Синтаксичний аналізатор для поняття “сума”

Задача. Скласти програму, яка реалізує синтаксичний аналізатор для поняття “сума”

де

• Sum – функція, що аналізує загальну суму;
• Integer – функція, що аналізує ціле число;
• Digit – функція, що аналізує цифру;
• Operation – функція, що реалізує знак операції. Знаком операції може бути ‘+’ або ‘–’.

Вираз, взятий у фігурні дужки { } може повторюватись.

Розв’язок. Використовуючи даний приклад як зразок, можна розробляти власні аналізатори складних виразів. Представлення кожного складного виразу може бути розбите на частини. Для кожної частини може бути розроблена власна рекурсивна функція.

Для розв’язку даної задачі розроблено 4 функції:

• функцію IsSignOp(), яка визначає чи символ c є знаком операції. Символ c передається у функцію як вхідний параметер. Функція повертає логічне значення true або false;
• функцію IsDigit(), яка визначає, чи вхідний символ c є цілим числом. Символ c є параметром функції;
• рекурсивну функцію IsInteger(), яка аналізує увесь вираз. Функція отримує 3 параметри. Перший параметр є рядком, який аналізується. Другий параметр pos є позицією поточного символу в рядку s, який аналізується. Третій, допоміжний параметр IsOp вказує, чи був попередній символ знаком операції. Третій параметр IsOp необхідний, щоб уникнути повторення двох знаків операцій, наприклад, “++”;
• функцію IsSum(), яка викликає рекурсивну функцію IsInteger(). Функція IsSum() здійснює просте перенаправлення на виконання функції IsInteger().

Реалізація функцій наступна:

// знак операції
static boolean IsSignOp(char c) {
  if ((c=='+') || (c=='-'))
    return true;
  else
    return false;
}

// ціле число
static boolean IsDigit(char c) {
  if ((c>='0') && (c<='9'))
    return true;
  else
    return false;
}

// рекурсивна функція IsInteger(), реалізує перевірку всього виразу,
// pos - поточна позиція символу з рядка s, який перевіряється
// IsOp=true, якщо попередній символ на верхньому рівні був знак операції
static boolean IsInteger(String s, int pos, boolean IsOp) {
  char c;
  if (pos==0) {
    // перший символ виразу
    // першим має бути ціле число (цифра)
    c = s.charAt(pos);
    if (IsDigit(c)) // якщо символ c є цифрою,
      return IsInteger(s,pos+1,false); // то перейти на перевірку наступного символу
    else
      return false;
  }
  else
    if (pos<s.length()-1) {
      // середина та закінчення виразу
      c = s.charAt(pos);
      if (IsDigit(c)) // якщо число (цифра)
        return IsInteger(s,pos+1,false); // то обробити наступний символ
      else {
        // якщо не число (цифра)
        if (IsSignOp(c)) {
          // якщо знак операції,
          if (!IsOp) // якщо попередній знак не є знак операції,
            return IsInteger(s,pos+1,true); // то подивитися наступний символ
          else
            return false; // інакше помилка у виразі: підряд слідують 2 знаки операції
        }
        else
          return false; // помилка, у виразі недопустимий символ
      }
    }
    else {
      // кінець виразу
      c=s.charAt(pos);
      return IsDigit(c); // останній символ виразу має бути число (цифра)
    }
}

// функція IsSum(), яка викликає рекурсивну функцію IsInteger()
static boolean IsSum(String s) {
  // викликати рекурсивну функцію IsInteger()
  return IsInteger(s, 0, false);
}

Використання функції IsSum() в іншому програмному коді:

boolean b;
b = IsSum("253+23"); // b = true
b = IsSum("2345w-18"); // b = false
b = IsSum("750-450+200"); // b = true
b = IsSum("-200"); // b = false
b = IsSum("2019"); // b = true
b = IsSum("210+-5"); // b = false
b = IsSum("300-"); // b = false
b = IsSum("4564+2+"); // b = false

---

  ⇑

8. Перевід з однієї системи числення в іншу

Задача. Написати рекурсивну функцію переводу з десяткової системи числення у двійкову.

Розв’язок. Алгоритм переводу класичний. Потрібно вхідний параметр num ділити на 2 до тих пір, поки num>2. При кожному поділі потрібно виділяти остачу з допомогою виразу num%2. Операція % призначена для виділення остачі від ділення двох чисел.

Функція Convert10to2() отримує два аргументи:

• аргумент беззнакового цілого типу, якому відповідає параметр з іменем num. Це є задане число в десятковій системі числення.
• тимчасовий аргумент, що служить для запам’ятовування поточного результату у двійковій системі числення. Це є рядок res типу String.

Результатом функції є обернений до рядка res рядок типу String. Оскільки, при поділі, результуюче значення формується у зворотньому порядку.

Функція має наступну реалізацію:

// перевід натурального числа з 10-ї системи в двійкову
static String Convert10to2(int num, String res) {
    if (num<2) {
        if (num==0)
            res = res + "0";
        else
            res = res + "1";

        // реверсування рядка res і повернення результату
        String res2 = "";
        for (int i=res.length()-1; i>=0; i--)
            res2 += res.charAt(i);
        return res2;
    }
    else
    {
        if (num%2==0)
            res = res + "0";
        else
            res = res + "1";
        return Convert10to2(num/2,res); // перейти на наступний крок
    }
}

Використання функції в іншому методі

String res;
res = Convert10to2(19,""); // res = 10011
res = Convert10to2(119,""); // res = 1110111
res = Convert10to2(250,""); // res = 11111010

  ⇑

9. Рекурсивна функція Min(). Пошук мінімального значення в масиві типу double[]

Задача 1. Розробити рекурсивну функцію Min() пошуку мінімального значення в масиві A, який містить n чисел типу double (n>0).

Розв’язок. Для забезпечення циклічного процесу, в функцію Min() потрібно передавати додаткові параметри:

• A – масив, в якому здійснюється пошук мінімального значення;
• item – індекс елементу масиву, який порівнюється з поточним мінімальним значенням;
• min – поточне мінімальне значення.

 

// Рекурсивна функція, що обчислює мінімум в масиві A.
// Параметри функції:
// - A - масив, який розглядається;
// - item - номер елементу, який порівнюється з мінімумом;
// - min - поточний мінімум, результат.
public static double Min(double[] A, int item, double min) {
  // Обчислити мінімум
  if (min>A[item])
    min = A[item];      

  // Перевірка, чи останній елемент
  if (item == A.length-1) // якщо останній елемент, то повернути мінімум
    return min;
  else // якщо не останній елемент, то викликати рекурсивно функцію Min
    return Min(A, item+1, min);
}

Використання функції Min() може бути, наприклад, таким

...

// Тестувальний масив
double[] A = { 2.8, -1.3, 2.9, -1.5, -1.0, 2.2, 0, 3.7 };
double res;
res = Min(A, 1, A[0]);
System.out.println("Min = " + res);

...

  ⇑

10. Рекурсивна функція ConvertAnyR(). Перевід числа з однієї системи числення в іншу

Розробити рекурсивну функцію ConvertAny() переводу числа з системи числення з основою m у систему числення з основою n. Функція повинна отримувати наступні параметри:

• число num, яке потрібно перевести з системи числення m в систему числення n: num(m) ⇒ num(n);
• цілочисельне беззнакове число m, що задає номінал системи числення з основою m. Причому 2<m≤10;
• цілочисельне беззнакове число n, що задає номінал системи числення з основою n. Причому 2<n≤10.

Функція повинна повертати рядок типу String, який є результатом.

Розв’язок. Щоб конвертувати число з системи числення з основою m в систему числення з основою n, потрібно виконати таку послідовність дій:

• спочатку конвертувати число з системи числення m у десяткову систему числення;
• конвертувати число з десяткової системи числення у систему числення з основою n.

З метою порівняння нижче наведено розв’язок задачі двома способами:

• з використанням нерекурсивної функції ConvertAny();
• з використанням рекурсивної функції ConvertAnyR(). Дана функція використовує додаткову рекурсивну функцію ConvertTo10R() для переводу числа в десяткову систему числення.

Текст нерекурсивної функції наступний

// Нерекурсивна функція, яка переводить число з однієї системи числення в іншу
// m = 2..10, n = 2..10
public static String ConvertAny(long num, int m, int n) {
  String res = ""; // результат
  long t;
  int i;
  long num10;

  // 1. Перевірка на коректність даних
  if ((m<2)||(m>10)||(n<2)||(n>10))
    return "Incorrect data";

  // 2. Спочатку потрібно конвертувати число num(m) => num(10) - у десяткову систему числення
  num10 = 0; // число у десятковій системі числення
  i = 0;

  while (num>0) {
    t = (num % 10) * (long)Math.pow(m, i);
    num10 += t;
    num = num / 10;
    i = i+1;
  }

  // 2. Конвертувати число num10 у число в системі числення n
  while (num10>0) {
    t = num10%n;
    res = String.valueOf(t) + res;
    num10 = num10/n;
  }

  return res;
}

Використання нерекурсивної функції може бути, наприклад, таким

...

// Конвертувати число 22 з системи числення з основою 3
// в систему числення з основою 5
String number = ConvertAny(22, 3, 5);
System.out.println("number = " + number);

...

Текст рекурсивних функцій ConvertTo10R() та ConvertAnyR() подано нижче

// Рекурсивна функція, яка конвертує число в систему числення 10
public static long ConvertTo10R(long num, int m, int i) {
  long t;

  if (num>0) {
    t = (num%10) * (long)Math.pow(m, i);
    return t + ConvertTo10R(num/10, m, i+1);
  }
  else {
    return 0;
  }
}

// Рекурсивна функція, яка переводить число з однієї системи в іншу
public static String ConvertAnyR(long num, int m, int n) {
  long t;
  long num10;

  // 1. Перевірка даних на коректність
  if ((m<2)||(m>10)||(n<2)||(n>10))
    return "Incorrect data";

  if (m==10) {
    // Конвертувати в систему числення з основою n
    if (num>0) {
      t = num%n;     // взяти останнє число
      return ConvertAnyR(num/n, 10, n) + String.valueOf(t);
    }
    else {
      return "";
    }
  }
  else {
    // Спочатку перевести в 10-ву систему числення
    num10 = ConvertTo10R(num, m, 0);

    // Потім викликати рекурсивну функцію
    return ConvertAnyR(num10, 10, n);
  }
}

Приклад використання рекурсивної функції ConvertAnyR() наведено нижче

...

// Конвертувати число 22 з системи числення з основою 3
// в систему числення з основою 5
String numberR = ConvertAnyR(22, 3, 5);
System.out.println("numberR = " + numberR);

...

  ⇑

11. Рекурсивна функція isPrime(). Визначити, чи число є простим

Задача. Розробити рекурсивну функцію, яка визначає, чи являється задане натуральне число N простим. Просте число, це число N>1 яке не має інших дільників крім 1 та самого себе.

Розв’язок. Простим вважається ціле число, яке ділиться на 1 та на себе націло. Наприклад, прості числа це 2, 3, 5, 17 тощо.

Рекурсивна функція isPrime() повертає true, якщо число просте. В противному випадку функція повертає false

// Рекурсивна функція, яка визначає, чи є число простим
public static boolean isPrime(int num, int tnum, int k)
{
  if (tnum>1) {
    // Якщо число num ділиться на tnum націло, то збільшити k
    if ((num%tnum)==0)
      k++;

    // Перейти до наступної ітерації, зменшивши tnum на 1
    return isPrime(num, tnum-1, k);
  }
  else {
    k++;
    if (k>2)
      return false;
    else
      return true;
  }
}

Виклик функції з іншого методу може бути, наприклад, таким

...

// Визначити, чи число 25 є простим
boolean f = isPrime(25, 25, 0);
System.out.println("isPrime(25) = " + f);

// Визначити, чи число 2 є простим
f = isPrime(2, 2, 0);
System.out.println("isPrime(2) = " + f);

...

  ⇑

 

---

Зв’язані теми

• Рекурсія. Приклади розв’язку задач. Переваги та недоліки рекурсії

  ⇑

---