Примеры решения задач на рекурсию в языке программирования C++
Содержание
- 1. Вычисление площади треугольника
- 2. Вычисление квадрата числа
- 3. Комбинаторная задача
- 4. Синтаксический анализатор для понятия «идентификатор»
- 5. Значение функции Аккермана
- 6. Синтаксический анализатор для понятия «простое выражение»
- 7. Синтаксический анализатор для понятия «сумма»
- 8. Перевод из одной системы исчисления в другую
- 9. Задачи для повторения
- Связанные темы
Поиск на других ресурсах:
1. Вычисление площади треугольника
Задача. Задан треугольник размером m×n, где m, n – целые числа и m>0, n>0. Разработать рекурсивную функцию, которая вычисляет площадь треугольника на основе зависимости:
Решение. Если известна зависимость, то реализация функции не представляет особых проблем. Остановка рекурсивного процесса будет осуществляться при выполнении условия n=m=1.
Программный код функции S() следующий:
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
Из этой зависимости получается формула рекурсии:
Решение.
// расчет квадрата числа 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 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 k; k = C(6,4); // k = 15 k = C(4,3); // k = 4
4. Синтаксический анализатор для понятия «идентификатор»
Задача. Разработать рекурсивную функцию, которая реализует синтаксический анализатор для понятия идентификатор. Как известно, в языке программирования C++ идентификатор подчиняется следующим правилам:
- первым символом идентификатора обязательно есть буква латинского алфавита;
- второй, третий и т.д. символ идентификатора может быть буквой или цифрой.
Общая формула идентификатора следующая:
где
- identifier – некоторый идентификатор;
- letter – некоторая буква латинского алфавита (от ‘a’ до ‘z’ или от ‘A’ до ‘Z’);
- digit – цифра от ‘0’ до ‘9’.
Решение. В данном случае реализуется рекурсивная функция с именем IsIdentifier(). Поскольку, функция анализирует понятие «идентификатор», то результатом возврата из функции есть значение типа bool. Если функция возвращает true, то имя идентификатора корректно в соответствии с условием задачи. Если функция возвращает false, то в имени идентификатора есть ошибка.
Входным параметром рекурсивной функции IsIdentifier() есть строка типа string. Эта строка содержит название идентификатора. Просмотр идентификатора осуществляется от конца к началу. Условием окончания рекурсивного процесса есть достижение первого символа идентификатора.
Текст метода IsIdentifier() следующий
// метод, который определяет, корректно ли имя идентификатора bool IsIdentifier(string s, unsigned 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 = 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; }
Использование функции IsIdentifier() в другом программном коде
bool b; b = IsIdentifier("Aa13209", 0); // b = true b = IsIdentifier("5A", 0); // b = false
5. Значение функции Аккермана
Задача. Вычислить значение функции Аккермана для двух неотрицательных целых чисел n и m, где
Решение. Если известны зависимости, то реализация функции не есть трудной задачей. В соответствии с условием задачи функция получает два параметра. Это есть неотрицательные целые числа n и m. Возвращает функция также целое неотрицательное число.
При больших значениях n и m может возникнуть переполнение стека, так как функция Аккермана есть дважды рекурсивной: один из аргументов функции есть та же рекурсивная функция.
Реализация функции следующая:
// функция Аккермана unsigned int A(unsigned int n, unsigned 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)); }
Использование функции для малых значений n и m:
unsigned 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
6. Синтаксический анализатор для понятия «простое выражение»
Задача. Составить программу, которая реализует синтаксический анализатор для понятия «expression»
где
- Expression – некоторое простое выражение;
- simple_identifier – некоторый простой идентификатор;
- letter – буква латинского алфавита от ‘a’ до ‘z’ или от ‘A’ до ‘Z’;
- operation – знак операции ‘+’, ‘–’ или ‘*’.
Решение. Для решения данной задачи нужно реализовать три функции:
- функцию IsIdentifier(), которая определяет есть ли простой идентификатор буквой;
- функцию IsOperation(), которая определяет ли есть операция синтаксически верной в соответствии с условием задачи;
- рекурсивную функцию IsExpression(), которая определяет есть ли простое выражение синтаксически правильным в соответствии с условием задачи.
Рекурсивная функция IsExpression() получает 3 параметра:
- строку s, которая анализируется;
- позицию pos текущего символа в строке s;
- флажок IsOp, определяющий был ли предыдущий символ знаком операции.
Реализация функций IsIdentifier(), IsOperation() и IsExpression() следующая:
// простой идентификатор bool IsIdentifier(char c) { // проверка, есть ли символ c литерой if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z')) return true; else return false; } // знак операции bool IsOperation(char c) { if ((c=='-') || (c=='+') || (c=='*')) return true; else return false; } // Рекурсивная функция-анализатор выражения, bool IsExpression(string s, unsigned int pos, bool IsOp) { char c; c = s[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() в другом методе:
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().
Реализация функций следующая:
// синтаксический анализатор для понятия "сумма" // знак операции bool IsSignOp(char c) { if ((c=='+') || (c=='-')) return true; else return false; } // цифра bool IsDigit(char c) { if ((c>='0') && (c<='9')) return true; else return false; } // рекурсивная функция IsInteger(), реализует проверку всего выражения, // pos - текущая позиция символа из строки s, которая анализируется // IsOp=true, если предыдущий символ на верхнем уровне был знаком операции bool IsInteger(string s, int pos, bool IsOp) { char c; c = s[pos]; // взять символ для обработки if (pos==0) // начало выражения { // первым может идти целое число if (IsDigit(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)) // символ c есть знак операции? { // если знак операции, то посмотреть предыдущий символ в переменной IsOp if (!IsOp) return IsInteger(s,pos+1,true); // если предыдущий символ не знак операции, то продолжить дальше else return false; // если предыдущий символ знак операции, то есть ошибка: два знака операции не могут быть рядом } else return false; // если не число и не знак операции, то в выражении ошибка - присутствует недопустимый символ } } else // конец выражения return IsDigit(c); // последний символ выражения обязательно должно быть число (цифра) } // функция IsSum(), которая вызывает рекурсивную функцию IsInteger() 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+-5"); // b = false b = IsSum("300-"); // b = false
8. Перевод из одной системы исчисления в другую
Задача. Написать рекурсивную функцию перевода из десятичной системы исчисления в двоичную.
Решение. Алгоритм перевода классический. Нужно входной параметр num делить на 2 до тех пор, пока num>2. При каждом делении нужно выделять остаток с помощью выражения num%2. Операция % предназначена для выделения остатка от деления двух чисел.
Функция Convert10to2() получает два аргумента:
- аргумент беззнакового целого типа, которому соответствует параметр с именем num. Это есть заданное число в десятичной системе исчисления.
- временный аргумент, который служит для запоминания текущего результата в двоичной системе исчисления. Это есть строка res типа string.
Результатом функции есть обратная (реверсивная) к строке res строка типа string. Поскольку, при делении, результирующее значение формируется в обратном порядке.
Функция имеет следующую реализацию:
// перевод натурального числа из 10-й системы в двоичную string Convert10to2(unsigned int num, string res) { if (num<2) { if (num==0) res.append("0"); else res.append("1"); // реверсирование строки res и возврат результата string res2=""; for (int i=res.length()-1; i>=0; i--) res2.push_back(res[i]); return res2; } else { if (num%2 == 0) res.append("0"); else res.append("1"); return Convert10to2((unsigned int)num/2, res); // перейти на следующий шаг } }
Использование функции в другом программном коде
string result; string s=""; result = Convert10to2(255,s); // res = 11111111 result = Convert10to2(83,s); // res = 1010011 result = Convert10to2(23,s); // res = 10111 result = Convert10to2(0,s); // res = 0
9. Задачи для повторения
Задача 1. Разработать рекурсивную функцию Min() поиска минимального значения в массиве A, который содержит n чисел типа double (n>0).
Решение можно посмотреть здесь.
Задача 2. Разработать рекурсивную функцию ConvertAny() перевода числа из системы исчисления с основой m в систему исчисления с основой n. Функция должна получать следующие параметры:
- число num, которое нужно перевести из системы исчисления m в систему исчисления num(m)⇒num(n);
- целочисленное беззнаковое число m, задающее номинал системы исчисления с основой m. Причем 2<m≤9;
- целочисленное беззнаковое число n, задающее номинал системы исчисления с основой n. Причем 2<n≤9.
Функция должна возвращать строку типа string, которая есть результатом.
Решение можно посмотреть здесь.
Задача 3. Разработать рекурсивную функцию, которая определяет, является ли заданное натуральное число N простым. Простое число, это число N>1 которое не имеет других делителей кроме 1 и самого себя.
Решение можно посмотреть здесь.