Рекурсия_в_язые_программирования_в_С#

1.

Рекурсия в языке
программирования C#
В данной презентации мы рассмотрим
концепцию рекурсии в языке
программирования C#, включая её
определение и примеры использования.
Мы обсудим базовые и рекурсивные
случаи, эффективность и ограничения
рекурсивных функций, а также хвостовую
рекурсию. Также мы рассмотрим примеры
применения рекурсии в C# и сделаем
выводы о её использовании в
программировании.

2.

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

3.

Примеры рекурсивных функций
Рекурсивные функции в C# широко применяются для решения задач,
связанных с обходом структур данных, таких как деревья и списки. Например,
функция для вычисления факториала числа использует рекурсию,
последовательно уменьшая аргумент и возвращая произведение до
достижения базового случая.
Ещё один пример — рекурсивная функция для обхода каталогов, которая
вызывает саму себя для каждого подкаталога, обеспечивая рекурсивное
выполнение задачи.

4.

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

5.

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

6.

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

7.

Пример РЕКУРСИИ - ФАКТОРИАЛ
Возьмем, к примеру, вычисление факториала, которое использует формулу n! = 1 *
2 * … * n. То есть по сути для нахождения факториала числа мы перемножаем все
числа до этого числа. Например, факториал числа 4 равен 24 = 1 * 2 * 3 * 4, а
факторил числа 5 равен 120 = 1 * 2 * 3 * 4 * 5.
Определим метод для нахождения факториала:

8.

При создании рекурсивной функции в ней обязательно должен быть
некоторый базовый вариант, с которого начинается вычисление функции.
В случае с факториалом это факториал числа 1, который равен 1.
Факториалы всех остальных положительных чисел будет начинаться с
вычисления факториала числа 1, который равен 1.
На уровне языка программирования для возвращения базового варианта
применяется оператор return:

9.

При создании рекурсивной функции в ней обязательно должен быть
некоторый базовый вариант, с которого начинается вычисление функции.
В случае с факториалом это факториал числа 1, который равен 1.
Факториалы всех остальных положительных чисел будет начинаться с
вычисления факториала числа 1, который равен 1.
На уровне языка программирования для возвращения базового варианта
применяется оператор return:

10.

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