Рекурсия – вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия). Например, функция A вызывает функцию B, а функция B – функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Одна из ключевых задач рекурсивного метода – предотвращение бесконечной рекурсии.
Реализация рекурсивных вызовов функций, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно.
На каждый рекурсивный вызов требуется некоторое количество оперативной памяти, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Не используйте рекурсию для вычисления факториалов и чисел Фибоначчи.
Пример сложной рекурсии:
static void Recursion(int counter)
{
counter--;
Console.WriteLine("Первая половина метода Recursion: {0}", counter);
if (counter != 0)
Method(counter);
Console.WriteLine("Вторая половина метода Recursion: {0}", counter);
}
static void Method(int counter)
{
Console.WriteLine("Первая половина метода Method: {0}", counter);
Recursion(counter);
Console.WriteLine("Вторая половина метода Method: {0}", counter);
}
static void Main()
{
Method(3);
// Delay.
Console.ReadKey();
}
В данном примере метод Recursion вызывает метод Method, который внутри себя вызывает метод Recursion, таким образом, метод Recursion будет вызываться рекурсивно.
Использование техники сложной рекурсии сложнее обнаружить, нежели использование обычной рекурсии, поскольку нужно просматривать работу обоих методов, соответственно контролировать работу сложной рекурсии сложнее.
Источник: видеоурок Александра Шевчука "МЕТОДЫ. РЕКУРСИЯ"
предыдущая статья