Рекурсивные методы в C#

Рекурсивные методы — это методы, которые вызывают сами себя. Использование рекурсии позволяет сократить исходный код программы и, иногда, сделать его более понятным.

Рекурсивные методы в C#

Рекурсия — это процесс, при котором метод многократно вызывает сам себя до тех пор, пока не будет выполнено определённое условие. Исходя из этого определения можно сделать следующий вывод: в рекурсивном методе обязательно должно быть определено условие выхода из метода. Если этого не сделать, то метод будет вызывать сам себя бесконечное количество раз. Рекурсия чем то похода на цикл: пока выполняется условие цикла, цикл работает, и точно так же, пока выполняется условие, метод будет вызывать сам себя.

Чтобы понять как работает рекурсивный метод, рассмотрим классический пример такого метода – вычисление факториала.

Пример рекурсии – вычисление факториала

Вычисление факториала числа — это, самая популярная задача, решаемая практически всеми студентами на всевозможных языках программирования. Из курса математики мы знаем, что:

1. факториал 0 равен 1
2. факториал 1 равен 1
3. факториал отрицательного числа не существует
4. факториал положительного числа, например, 5 будет равен 1*2*3*4*5 = 120 и записывается как 5! = 1*2*3*4*5 = 120

Чтобы написать программу, вычисляющую факториал мы можем использовать обычные циклы, а можем написать свой рекурсивный метод:

static int Factorial(int n)
{ 
    if ((n == 0)||(n==1))
        return 1;
    return n * Factorial(n - 1);
}

Воспользуемся этим методом, например, в консольном приложении следующим образом:

Console.Write("Введите целое число: ");
int a = Convert.ToInt32(Console.ReadLine());
Console.WriteLine(Factorial(a));
Console.ReadKey();

static int Factorial(int n)
{
    if ((n == 0) || (n == 1))
        return 1;
    return n * Factorial(n - 1);
}

Запустим приложение и проверим работу нашего метода, например, вычислив факториал 3:

Схематично, работу нашего метода можно представить следующим образом:

Рекурсивный метод обязательно должен содержать в себе условие выхода из метода. В примере с факториалом — это условие if:

if ((n == 0) || (n == 1))

как только n станер равной 1 или в метод передадут 0, то работа метода завершается — срабатывает оператор return. Внутри метода, если условие выхода не выполняется, он вызывает сам себя:

return n * Factorial(n - 1);

На каждом шаге выполнения метода до достижения условия выхода из рекурсии в стеке создается запись о вычислении. Как только достигается условие выхода, записи возвращаются из стека и производится окончательное вычисление значения метода.

Недостатки рекурсивных методов в C#

Практически всегда рассматриваются достоинства рекурсивных методов (краткость, легкость восприятия кода и т.д.) и, при этом, достаточно редко акцентируется внимание на недостатках, о которых всегда стоит помнить.

Сложность отладки рекурсивных методов

Рекурсивные методы тяжелее проверять на корректность вычислений, чем обычные методы, например, с циклами. При использовании рекурсии нередко приходится отслеживать и то, что попадает в стек и то, что, в итоге возвращается из стека.

Попадание в бесконечную рекурсию и переполнение стека

Как было указано выше, одним из главнейших условий при разработке рекурсивного метода — это наличие условия выхода из метода (или, как ещё говорят — базового сценария). Если рекурсивный метод достаточно большой, то можно упустить этот момент и тогда метод будет вызывать себя до тех пор, пока не произойдет переполнение стека. Например, уберем из нашего метода условие ifи попробуем запустить программу. Достаточно быстро вы увидите в консоли вместо решения ошибку вот такого плана:

При этом, чем больше будет в рекурсивном методе различных вычислений, тем быстрее произойдет переполнение стека.

Большее время выполнения по сравнению с обычными методами

Из-за постоянной работы со стеком, рекурсивные методы могут работать медленнее, чем обычные методы.

Подведем итог

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

Домашнее задание №18

Составьте программу для вычисления и вывода n-го числа Фибоначчи с использованием рекурсии