Примеры решения задач на рекурсию на 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. Синтаксический анализатор для понятия «идентификатор»

Задача. Разработать рекурсивную функцию, которая реализует синтаксический анализатор для понятия идентификатор. Как известно, в языке программирования C# идентификатор подчиняется следующим правилам:

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

Общая формула идентификатора следующая:

где

• 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() следующая:

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

// определяет, есть ли символ c знаком операции
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 в систему исчисления 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

⇑