Въведение в рекурсивната функция в С
Процесът на повторение на предметите по подобен начин, както беше преди, е известен като рекурсия. Казва се, че функцията е рекурсивна, ако се извиква в себе си. Рекурсията се поддържа от езика за програмиране C. По-долу са посочени две условия, които са критични за реализирането на рекурсия в C:
- Условие за изход: Това състояние помага на функцията да определи кога да излезе от тази функция. В случай, че не посочим условието за изход, кодът ще влезе в безкраен цикъл.
- Промяна на брояча: Промяна на брояча при всяко повикване към тази функция.
По този начин можем да реализираме рекурсивна функция в езика за програмиране на С. Тези функции са полезни за решаване на математически проблеми с пари, които изискват подобен процес да бъде извикан няколко пъти. Примери за такива проблеми са изчисляването на фактологията на редица поколения от серии на Фибоначи.
Синтаксис:
int fun(a1)
(
If(base_condition) return val;
fun(a2);
)
Как работи рекурсивната функция в C?
Рекурсивните функции са начинът за прилагане на уравнението в езика за програмиране на С. Извиква се рекурсивна функция с аргумент, предаден в нея, например n, паметта в стека е разпределена на локалните променливи, както и на функциите. Всички операции, присъстващи във функцията, се извършват с помощта на тази памет. Условието за излизане се проверява дали той отговаря. Когато компилатор открие повикване към друга функция, той незабавно разпределя нова памет в горната част на стека, където се създава различно копие на същите локални променливи и функцията се създава. Въведете същия процес продължава.
Когато основното състояние върне вярно, конкретната стойност преминава към извикващата функция. Паметта, отредена за тази функция, се изчиства. подобно новата стойност се изчислява във функцията за повикване и ИТ се връща към функцията за супер извикване. По този начин се правят рекурсивни повиквания за изтриване на функцията достига до първата функция и цялата памет на стека се изчиства и изходът се връща. Основното състояние или състоянието на изход не са посочени във функцията, тогава рекурсивните повиквания към функцията могат да доведат до безкраен цикъл.
Пример за рекурсивна функция
Сега ще видим примерите на рекурсивна функция в 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.
)
изход:
Обяснение на горния код
Горепосоченият пример е намирането на фактория на число. Когато основната функция извиква забавление (4), тогава първо се проверява условието за изход (4 == 1), след това се извиква 4 * забавно (3). Отново се проверява основното състояние (3 == 1). По същия начин, той ще върне 3 * забавление (2) се извиква и това продължава до 2 * забава (1) се извиква и където тя отговаря на основното условие и връща 1, след това функция за повикване връща 2 * 1 след това, 3 * 2 * 1 и от първото повикване 4 * 3 * 2 * 1 се връща. Така резултатът в основните функции съхранява 24 и отпечатва това на изхода.
Разпределение на паметта на рекурсивна функция
Всеки разговор към функция на език c води до разпределение на паметта в горната част на стека. Когато се нарича рекурсивна функция, паметта се разпределя към нея в горната част на паметта, която е разпределена за извикващата функция с всички различни копия на локални променливи, се създават за всяко повикване към функцията.
Какво е постигнато основното състояние, паметта, разпределена за функцията, се унищожава и показалецът се връща към извикващата функция? този процес се повтаря след това първата функция за повикване и най-сетне, паметта на стека се изпразва.
В дадения по-горе пример за изчисляване на коефициента на число по-долу е сценарият за разпределение на паметта.
Етап 1
Стъпка 2
Стъпка - 3
Стъпка - 4
Стъпка - 5
Стъпка - 6
Стъпка - 7
Стъпка - 8
Стъпка - 9
Видове рекурсия
Има два типа рекурсия в програмирането на С, които са дадени по-долу:
1. Опашка и не-опашна рекурсия
Горепосоченият тип рекурсия е обяснен по-долу:
- Рекурсия на опашката
Това е вид рекурсивен призив за рекурсия във функцията, който е последното действие, което се извършва при дефиницията на функцията. Означава, че рекурсивният разговор се появява, след като се реализира цялата останала логика във функцията.
Използването на опашка рекурсия в нашата програма за изпълнение на програмата и също така намалява използването на паметта на тази функция. Това е така, тъй като като друга логика във функцията е приложена към паметта, отредена за извикващата функция, може да бъде премахната от стека и да се използва повторно.
Код:
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. Можете също да разгледате следните статии, за да научите повече-
- Масиви в C програмиране
- Палиндром в програма C
- Модели в C програмирането
- C срещу C ++
- Палиндром в JavaScript
- Ръководство за сериите на Фибоначи в JavaScript