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

Вступ до рекурсивної функції в С

Вступ до рекурсивної функції в С

Процес повторення предметів аналогічним чином, як це було раніше, відомий як рекурсія. Кажуть, що функція є рекурсивною, якщо вона викликається всередині себе. Рекурсія підтримується мовою програмування C. Нижче наведено дві умови, які є критичними для впровадження рекурсії в C:

Умова виходу: Ця умова допомагає функції визначити, коли потрібно вийти з цієї функції. Якщо ми не вкажемо умову виходу, то код увійде в нескінченний цикл.
Зміна лічильника: Зміна лічильника при кожному дзвінку до цієї функції.

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

Синтаксис:

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

Як працює рекурсивна функція в C?

Рекурсивні функції - це спосіб реалізації рівняння в мові програмування C. Рекурсивна функція викликається аргументом, переданим в неї, скажімо, n, пам'ять у стеці розподіляється на локальні змінні, а також функції. Усі операції, присутні в функції, виконуються за допомогою цієї пам'яті. Умова виходу перевіряється, чи він відповідає. Коли компілятор виявляє виклик до іншої функції, він негайно виділяє нову пам’ять у верхній частині стека, де створюється інша копія тих же локальних змінних і функція створюється. Введіть той же процес, що продовжується.

Коли базова умова повертає істинне, конкретне значення передається функції виклику. Очищена пам'ять, виділена на цю функцію. аналогічно, нове значення обчислюється у функції виклику, а ІТ повертається до функції супервиклику. Таким чином здійснюються рекурсивні виклики, щоб функція видалення досягає першої функції, і вся пам'ять стека очищається, а вихід повертається. Базовий стан або умова виходу не визначені у функції, тоді рекурсивні виклики до функції можуть призвести до нескінченного циклу.

Приклад рекурсивної функції

Тепер ми розглянемо приклади рекурсивної функції в С

Код:

#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 * 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

Види рекурсії

Нижче наведено два типи рекурсії в програмуванні на С:

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 - Повне керівництво по рекурсивній функції в С