Курс — «Программирование на C для начинающих». Функции. #15 Рекурсия
Здравствуйте, дорогие друзья.
Рекурсия — это концепция в программировании, при которой функция вызывает саму себя для решения задачи. Рекурсивные функции позволяют решать сложные задачи путем разбиения их на более простые подзадачи. В этом разделе мы рассмотрим основные принципы рекурсии, примеры рекурсивных функций и их применение.
Основные принципы рекурсии
Рекурсивная функция состоит из двух основных частей:
- Базовый случай: Условие, при котором функция прекращает вызывать саму себя и возвращает результат. Базовый случай предотвращает бесконечную рекурсию.
- Рекурсивный случай: Условие, при котором функция вызывает саму себя с измененными параметрами, чтобы решить более простую подзадачу.
Пример рекурсивной функции: вычисление факториала
Факториал числа nn (обозначается как n!n!) — это произведение всех целых чисел от 1 до nn. Например, факториал числа 5 равен 5!=5×4×3×2×1=1205!=5×4×3×2×1=120.
Пример рекурсивной функции для вычисления факториала:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <stdio.h> // Рекурсивная функция для вычисления факториала unsigned long long factorial(unsigned int n) { if (n == 0) { return 1; // Базовый случай } else { return n * factorial(n - 1); // Рекурсивный случай } } int main() { unsigned int number = 5; printf("Factorial of %d is %llu\n", number, factorial(number)); return 0; } |
В этом примере функция factorial вычисляет факториал числа nn. Базовый случай — это когда nn равно 0, и функция возвращает 1. Рекурсивный случай — это когда функция вызывает саму себя с параметром n−1n−1 и умножает результат на nn.
Пример рекурсивной функции: вычисление чисел Фибоначчи
Числа Фибоначчи — это последовательность чисел, в которой каждое число является суммой двух предыдущих чисел. Например, первые несколько чисел Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13 и т.д.
Пример рекурсивной функции для вычисления чисел Фибоначчи:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <stdio.h> // Рекурсивная функция для вычисления чисел Фибоначчи unsigned long long fibonacci(unsigned int n) { if (n == 0) { return 0; // Базовый случай } else if (n == 1) { return 1; // Базовый случай } else { return fibonacci(n - 1) + fibonacci(n - 2); // Рекурсивный случай } } int main() { unsigned int number = 10; printf("Fibonacci number %d is %llu\n", number, fibonacci(number)); return 0; } |
В этом примере функция fibonacci вычисляет число Фибоначчи для заданного nn. Базовые случаи — это когда nn равно 0 или 1, и функция возвращает 0 или 1 соответственно. Рекурсивный случай — это когда функция вызывает саму себя с параметрами n−1n−1 и n−2n−2 и суммирует результаты.
Преимущества и недостатки рекурсии
Преимущества рекурсии:
- Простота и ясность: Рекурсивные функции часто бывают проще и понятнее, чем их итеративные аналоги.
- Естественное решение: Рекурсия естественным образом подходит для решения задач, которые можно разбить на более простые подзадачи.
Недостатки рекурсии:
- Производительность: Рекурсивные функции могут быть менее эффективными по сравнению с итеративными аналогами из-за накладных расходов на вызовы функций.
- Глубина рекурсии: Рекурсивные функции могут привести к переполнению стека, если глубина рекурсии слишком велика.
Рекурсия — это мощный инструмент в программировании, который позволяет решать сложные задачи путем разбиения их на более простые подзадачи. Понимание основных принципов рекурсии, таких как базовый и рекурсивный случаи, является важным навыком для начинающих программистов.
На этом все. Всем хорошего дня!