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

---

Зміст

• 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;
}

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

int k;
k = S(5,3); // k = 15
k = S(9,2); // k = 18

⇑

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;
}

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

int k;
k = f(9); // k = 81

⇑

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);
}

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

int nn;
nn = C(6, 4); // nn = 15
nn = C(4, 3); // nn = 4

⇑

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

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

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

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

де

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

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

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

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

// метод, що визначає, чи коректне ім'я ідентифікатора
static bool IsIdentifier(string s, int pos)
{
  if (pos == 0) 
  {
    char c;
    c = s[pos];
    // перевірка, чи перший символ літера
    if ((c >= 'a') && (c <= 'z') || (c >= 'A') && (c <= 'Z'))
      return IsIdentifier(s, pos + 1); // перехід до перевірки наступного символу
    else
      return false;
  }
  else
    if (pos < s.Length) // якщо не останній символ
    {
      char c;
      c = s[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; // якщо немає символів для перевірки, то ідентифікатор коректний
}

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

bool f;
f = IsIdentifier("A13yuu", 0); // f = true

⇑

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

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

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

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

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

// функція Аккермана
static uint A(uint n, uint 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));
}

Використання функції для малих n та m:

uint 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

⇑

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

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

де

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

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

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

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

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

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

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

// визначає, чи символ є знаком операції
static bool IsOperation(char c)
{
  if ((c == '-') || (c == '+') || (c == '*'))
    return true;
  else
    return false;
}

// Рекурсивна функція - аналізує, чи правильний вираз
static bool IsExpression(string s, uint pos, bool IsOp)
{
  char c;
  c = s[(int)pos];
  if (pos == 0) // якщо s[pos] - перший символ у виразі
  {
    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); // true - вказати на наступному рівні, що була операція
        else
          return false;
      }
    }
    else // обробити останній символ в рядку s
      return IsIdentifier(c); // перевірити, чи останній символ ідентифікатор
}

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

bool b;
b = IsExpression("a+b", 0, false); // b = true
b = IsExpression("+a+b", 0, false); // b = false
b = IsExpression("Adsdl-Bdslf-FDF", 0, false); // b = true
b = IsExpression("a+-b-c", 0, false); // b = false
b = IsExpression("a+b;", 0, false); // b = false
b = IsExpression("alsd+bsldk-", 0, false); // b = false
b = IsExpression("AbcDEf", 0, false); // b = 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 bool IsSignOp(char c)
{
  if ((c == '+') || (c == '-'))
    return true;
  else
    return false;
}

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

// рекурсивна функція IsInteger(), реалізує перевірку всього виразу,
// pos - поточна позиція символу з рядка s, який перевіряється
// IsOp=true, якщо попередній символ на верхньому рівні був знак операції
static bool IsInteger(string s, int pos, bool IsOp)
{
  char c;
  c = s[pos]; // взяти поточний символ, який обробляється

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

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

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

bool 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+-6"); // b = false
b = IsSum("300+"); // b = false

⇑

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

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

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

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

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

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

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

// перевід натурального числа з 10-ї системи в двійкову
static string Convert10to2(uint num, string res)
{
  if (num < 2)
  {
    uint t = num % 2;
    res = res + t.ToString();

    // реверсування рядка res і повернення результату
    string res2 = "";
    for (int i = res.Length-1; i>=0; i--)
      res2 = res2 + res[i];
    return res2;
  }
  else
  {
    uint t = num % 2;
    res = res + t.ToString();
    return Convert10to2(num / 2, res);
  }
}

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

string res;
res = Convert10to2(18, ""); // res = 10010
res = Convert10to2(39, ""); // res = 100111
res = Convert10to2(0, ""); // res = 0
res = Convert10to2(250, ""); // res = 11111010

⇑

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

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

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

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

 

using System;

namespace ConsoleApp12
{
  class Program
  {
    // Рекурсивна функція Min() - обчислення мінімуму в масиві.
    // Параметри:
    // - 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
        return Min(A, item + 1, min);
    }

    static void Main(string[] args)
    {
      // Тестувальний масив
      double[] A = { 2.3, 2.5, 1.8, 8.3, 11.2 };

      // Виклик статичної функції
      double min = Program.Min(A, 1, A[0]);
      Console.WriteLine("min = {0:f}", min); // min = 1.80
    }
  }
}

⇑

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

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

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

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

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

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

З врахуванням цього, розв’язок задачі представлено двома функціями:

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

 

using System;

namespace ConsoleApp12
{
  class Program
  {
    // Рекурсивна функція, яка конвертує число в десяткову систему числення
    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) + Convert.ToString(t);
        }
        else
          return "";
      }
      else
      {
        // Спочатку перевести в 10-ву систему числення
        num10 = ConvertTo10R(num, m, 0);

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

    static void Main(string[] args)
    {
      // Конвертувати число 58 з системи числення з основою 4
      // в систему числення з основою 6
      string numberR = ConvertAnyR(23, 4, 6);
      Console.WriteLine("number = {0}", numberR); 
    }
  }
}

⇑

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

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

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

using System;

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

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

    static void Main(string[] args)
    {
      // Визначити, чи число 25 є простим
      bool f = isPrime(25, 25, 0);
      Console.WriteLine("f = {0}", f);
    }
  }
}

Результат виконання програми

f = False

⇑

---

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

• Рекурсія. Приклади рекурсивних методів (функцій) в C#
• Приклади розв’язку задач на рекурсію в Java

⇑