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

---

Содержание

• 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() следующий

// определение, есть ли строка идентификатором
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[]

Задача. Разработать рекурсивную функцию 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);

...

⇑

---

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

• Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии

⇑

---