Известно, что процесс, в котором конкретная функция вызывает себя прямо или косвенно, является рекурсией, а соответствующая функция является рекурсивной функцией. Процесс рекурсии имеет дело с итерацией нескольких чисел для одной и той же функции. Чтобы завершить выполнение процесса рекурсии, нам нужно иметь базовый случай, за которым следует любое условие. В этом руководстве используются функции рекурсии в C ++, поэтому перед чтением вы должны быть знакомы с основами этого языка программирования.
Рекурсия — это эффективный подход к решению таких проблем, как сложные математические вычислительные задачи. Это делается путем разделения задачи на подзадачи. Этот процесс осуществляется в соответствии с правилом «разделяй и властвуй». Необязательно всегда использовать процесс рекурсии в вашей программе для повторения. Любая проблема, решаемая с помощью рекурсии, также может быть решена с помощью итераций. Но рекурсивная функция более эффективна в программировании, поскольку код очень короткий и легко понятный при выполнении той же задачи. Процесс рекурсии всегда рекомендуется для таких задач, как поиск и сортировка, обход дерева и т.д.
Примечание: процесс рекурсии должен иметь условие завершения или базовый класс. Во втором случае это приведет к бесконечному количеству выполнений, как цикл итераций.
Синтаксис рекурсивной функции (C ++)
Базовый синтаксис рекурсивной функции имеет следующий вид:
void recurse(){
// Statement(s)
recurse(); }
Идея состоит в том, чтобы разделить проблему на множество более мелких проблем, а затем добавить все базовые условия, которые могут остановить рекурсию.
Базовое состояние
В любой рекурсивной программе решение более крупной проблемы выражается в более мелких задачах.
int fact(int n)
{
if (n < = 1) // base case
return 1;
else
‘other statement’
}
Утверждение / условие «n <= 1» определяется здесь, и, следовательно, большее значение может быть решено путем преобразования в меньшее, пока не будет выполнено условие базового случая. Если мы не используем базовое условие в нашей программе, то не будет конечной точки, указывающей код, произойдет бесконечное выполнение. Здесь мы будем использовать примерный пример.
Простая функция
Теперь рассмотрим пример рекурсивной функции, в которой мы берем значение в основной программе и затем передаем его функции. Внутри функции мы используем оператор if-else. Часть оператора if относится к базовому условию завершения функции или ограничения вывода. Это будет применяться, когда значение меньше 1.
If (val < 1)
В то время как основная функция применяется к «else» части функции. Это рекурсивная функция.
# Function (val – 1)
Значение отображается до и после этого оператора, поэтому выходные данные будут содержать числа в порядке убывания и возрастания. Выполнение кода выполняется компилятором g ++. ’-o’ используется для сохранения вывода исходного кода в выходной файл.
$ g++ -o r1 r1.c
$ ./r1
Теперь мы хотим увидеть эффект базового условия в этой программе. Мы увидим результирующее значение; если мы удалим из той же программы оператор if-else, как описано выше, каким будет результат.
Вы можете видеть, что остальной код не изменился после удаления условного оператора. После удаления базового оператора результат будет выглядеть, как на изображении ниже. Для этого выполнения не будет определенной конечной точки. Вы можете заметить, что на выходе получается бесконечное число.
Этот же вывод занимает много строк, пока не появится сообщение о дампе ядра.
Работа рекурсии
Предположим, что программист хочет определить сумму первых n чисел, существует много способов определить сумму, но самый простой — сложить числа, начиная с 1 до n. Итак, функция будет выглядеть так:
F(n) = 1+2+3+4+5+…..+n
Приведенный выше пример представляет собой простое сложение чисел. Второй подход связан с использованием рекурсивной функции.
F(n) = 1 n=1
F(n)= n + f(n—1) n>1
Теперь вы можете указать на разницу между обоими подходами. Во втором подходе f () — это основное несходство, как оно само называется.
Рекурсия бывает двух типов. Один из них — прямая рекурсия. Второй — косвенная рекурсия. Функция называется косвенной рекурсивной, если у нее есть вызов другой функции и эта другая функция прямо или косвенно вызывает первую функцию. Пример прямой рекурсии проиллюстрирован как:
Int f (int n) {
F (n);
//some code}
В то время как образец для косвенной рекурсии представлен как:
void f (int n) {
f1(); }
void f1( int n) {
f();
return; }
Теперь мы подробно рассмотрим оба типа рекурсивных функций на некоторых основных примерах.
Прямая рекурсия
Пример 1
В этом примере рассматривается расчет ряда Фибоначчи. Опять же, концепция та же; здесь используется условный оператор, чтобы остановить условие; значение должно быть равно нулю. В противном случае, если значение равно 1 или 2, оно вернет 1. Поскольку для формирования этого ряда требуется 2 числа, поэтому число, используемое в основной программе, должно быть больше 2. Формула оператора для Фибоначчи записывается в ’ остальное искусство условия. В основном это рекурсия программы.
# Function (val – 1) + function ( val — 2))
В то время как основная функция инициирует функциональный вызов в обход значения. Это значение — число, до которого должен быть вывод. Вывод можно проверить через терминал Linux с помощью компилятора g ++.
Пример 2
В этом примере рассматривается факториальное вычисление числа. Для этого расчета число должно быть больше 1, поэтому здесь мы применили базовое условие; если эта часть оператора if выполняется, то программа завершается; в противном случае к числу применяется математическая операция.
Val * function (val – 1)
Это функция рекурсии, в которой ответ функции снова используется в вызове функции.
Полученное значение показано ниже.
Косвенная рекурсия
Мы применим тот же расчет факториала косвенно. Как мы описали ранее, при косвенной рекурсии функции не вызывают ее, поэтому для этой цели нам нужна другая функция. Возьмем пример, который выполняет две функции. В функции A функция рекурсии объявлена так же, как в предыдущем примере, но вызов функции предназначен для второй функции, Function-B. Функция B содержит тот же метод расчета и рекурсивный вызов функции A.
В основной программе выполняется вызов функции A.
Когда вы увидите результат, вы заметите, что ответ для обоих методов рекурсии одинаковый, но разница только в используемом подходе.
Заключение
«Рекурсивная функция C ++» имеет много преимуществ, поскольку она используется в процессах поиска и сортировки. Базовое условие играет основную роль в выполнении рекурсии, поскольку оно ограничивает вывод и бесконечное выполнение. Здесь объясняются часто используемые примеры, чтобы дать пользователю понимание рекурсии.
