Примеры решения задач на рекурсию в языке программирования Java

Примеры решения задач на рекурсию в языке программирования Java


Содержание


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, если известна зависимость

n2 = (n-1)2 + 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() следующий

// определение, есть ли строка идентификатором
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. Задачи для повторения

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

Решение можно посмотреть здесь.

Задача 2. Разработать рекурсивную функцию ConvertAny() перевода числа из системы исчисления с основой m в систему исчисления с основой n. Функция должна получать следующие параметры:

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

Функция должна возвращать строку типа String, которая есть результатом.

Решение можно посмотреть здесь.

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

Решение можно посмотреть здесь.


Связанные темы