У цьому посібнику ви навчитеся писати рекурсивні функції в програмуванні на С за допомогою прикладу.
Функція, яка викликає себе, відома як рекурсивна функція. І ця методика відома як рекурсія.
Як працює рекурсія?
void recurse () (… repeatse ();…) int main () (… repeatse ();…)
Рекурсія триває доти, доки не виконується якась умова для її запобігання.
Щоб запобігти нескінченній рекурсії, можна використовувати оператор if … else (або подібний підхід), коли одна гілка робить рекурсивний виклик, а інша - ні.
Приклад: Сума натуральних чисел з використанням рекурсії
#include int sum(int n); int main() ( int number, result; printf("Enter a positive integer: "); scanf("%d", &number); result = sum(number); printf("sum = %d", result); return 0; ) int sum(int n) ( if (n != 0) // sum() function calls itself return n + sum(n-1); else return n; )
Вихідні дані
Введіть додатне ціле число: 3 сума = 6
Спочатку метод sum()
викликається із main()
функції, номер якої передається як аргумент.
Припустимо, значення n всередині sum()
дорівнює 3 спочатку. Під час наступного виклику функції 2 передається sum()
функції. Цей процес триває, поки n не дорівнює 0.
Коли n дорівнює 0, if
умова не виконується, і else
частина виконується, повертаючи функцію сумою цілих чисел main()
.
Переваги та недоліки рекурсії
Рекурсія робить програму елегантною. Однак, якщо продуктивність життєво необхідна, використовуйте замість них цикли, оскільки рекурсія зазвичай набагато повільніша.
З огляду на це, рекурсія - важливе поняття. Він часто використовується в структурі даних та алгоритмах. Наприклад, часто використовується рекурсія в таких задачах, як обхід дерева.