✅ Рекурсивная функция в C - Полное руководство по рекурсивной функции в C

Введение в рекурсивную функцию в C

Введение в рекурсивную функцию в C

Процесс повторения элементов таким же образом, как это было раньше, известен как рекурсия. Функция называется рекурсивной, если она вызывается внутри себя. Рекурсия поддерживается языком программирования C. Ниже приведены два условия, которые имеют решающее значение для реализации рекурсии в C:

Условие выхода: это условие помогает функции определить, когда выйти из этой функции. Если мы не укажем условие выхода, то код войдет в бесконечный цикл.
Изменение счетчика: изменение счетчика при каждом вызове этой функции.

Таким образом, мы можем реализовать рекурсивную функцию на языке программирования C. Эти функции полезны для решения математических задач, требующих многократного вызова аналогичного процесса. Примерами таких задач являются вычисления факториала ряда генерации рядов Фибоначчи.

Синтаксис:

int fun(a1) ( If(base_condition) return val; fun(a2); )

Как работает рекурсивная функция в C?

Рекурсивные функции - это способ реализации уравнения на языке программирования Си. Рекурсивная функция вызывается с переданным ей аргументом, скажем, n, память в стеке выделяется как локальным переменным, так и функциям. Все операции, присутствующие в функции, выполняются с использованием этой памяти. Условие для выхода проверяется, если оно удовлетворяет. Когда компилятор обнаруживает вызов другой функции, он сразу же выделяет новую память в верхней части стека, где создается другая копия тех же локальных переменных и функции. Введите тот же процесс продолжается.

Когда базовое условие возвращает true, конкретное значение передается вызывающей функции. Память, выделенная для этой функции, очищается. аналогично, новое значение вычисляется в вызывающей функции, и ИТ возвращается в супер вызывающую функцию. Таким образом, рекурсивные вызовы выполняются, чтобы функция delete достигла первой функции, и вся память стека очищается и возвращается результат. Если в функции не указано базовое условие или условие выхода, то рекурсивные вызовы функции могут привести к бесконечному циклу.

Пример рекурсивной функции

Теперь мы будем смотреть примеры рекурсивной функции в C

Код:

#include int fun(int n) ( if(n==1) return 1 ; //exit or base condition which gives an idea when to exit this loop. return n*fun(n-1); //function is called with n-1 as it's argument . //The value returned is multiplied with the argument passed in calling function. ) int main()( int test=4; int result =0; result =fun(test); printf("%d", result);//prints the output result. )

Выход:

Объяснение вышеуказанного кода

Приведенный выше пример поиска факториала числа. Когда основная функция вызывает fun (4), сначала проверяется условие выхода (4 == 1), затем вызывается 4 * fun (3). Снова проверяется базовое условие (3 == 1). Аналогично, он вернет 3 * вызов fun (2), и это будет продолжаться до 2 * вызов fun (1) и когда он удовлетворяет базовому условию и возвращает 1, то вызов функции возвращает 2 * 1, затем 3 * 2 * 1 и с первого звонка 4 * 3 * 2 * 1 возвращается. Таким образом, результат в основной функции сохраняет 24 и печатает их на выходе

Распределение памяти рекурсивной функции

Каждый вызов функции на языке c приводит к выделению памяти на вершине стека. Когда рекурсивная функция вызывается, ей выделяется память в верхней части памяти, которая была выделена вызывающей функции, и для каждого вызова этой функции создаются разные копии локальных переменных.
Какое базовое условие достигается, память, выделенная для функции, уничтожается и указатель возвращается к вызывающей функции? этот процесс повторяется затем первой вызывающей функцией и, наконец, память стека становится пустой.

В приведенном выше примере для вычисления факториала числа ниже приведен сценарий выделения памяти.

Шаг 1

Шаг 2

Шаг 3

Шаг - 4

Шаг - 5

Шаг - 6

Шаг - 7

Шаг - 8

Шаг - 9

Типы рекурсии

Есть два типа рекурсии в C-программировании, которые приведены ниже:

1. Хвостовая и нехвостая рекурсия

Вышеуказанный тип рекурсии объясняется ниже:

Хвост Рекурсия

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

Использование хвостовой рекурсии в нашей программе в hansis повышает производительность программы, а также уменьшает использование памяти функцией так. Это связано с тем, что, поскольку другая логика в функции была реализована, память, выделенная для вызывающей функции, может быть удалена из стека и использована повторно.

Код:

int fun1(n)( printf(“the result is “); return fun1(n-1); ) void main() ( fun1(4); )

Нехвостая рекурсия

Этот тип рекурсии рекурсивного коллажа сделан в середине определения функции. Рекурсия мужских брюк завершена, и значения, возвращенные вызывающей функции, должны выполнить больше шагов, поэтому память не может быть очищена.

Код:

int fun1(n)( printf(“the result is “); return n* fun1(n-1); ) void main()( fun1(4); )

2. Прямая и косвенная рекурсия

Вышеуказанный тип рекурсии объясняется ниже:

Непрямая рекурсия

Говорят, что косвенная рекурсия происходит, когда определенная функция вызывается рекурсивным способом из другой функции.

Код:

int fun1()( fun2(); ) int fun2()( fun1(); // calling the procedure recursively using another function. ) void main()( fun1(); )

Прямая рекурсия

Говорят, что прямая рекурсия происходит, когда рекурсивный вызов функции выполняется в пределах ее собственного определения. '

Код:

int fun1()( fun1(); ) void main()( fun1(); )

Вывод

Можно легко сделать вывод, что рекурсивные функции в большинстве случаев важны для решения математических задач, которые требуют, чтобы подобный метод повторял всю логику до тех пор, пока не будет выполнено условие выхода. Множество задач, таких как Ханойские башни, обход деревьев, расчет глубины графиков.

Важно упомянуть базовое условие для рекурсивной функции. Требования к памяти и времени больше для рекурсивной программы по сравнению с итеративными, поэтому должны использоваться осторожно.

Рекурсивная функция в C - Полное руководство по рекурсивной функции в C