run-dev

,

Как работает рекурсия в C#

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

Основные принципы рекурсии

Рекурсивные функции состоят из двух частей:

  • Базовый случай — условие, при котором рекурсия прекращается.
  • Рекурсивный вызов — обращение функции к самой себе с изменёнными аргументами.

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

using System;

class Program
{
    static int Factorial(int n)
    {
        if (n <= 1) return 1; // Базовый случай
        return n * Factorial(n - 1); // Рекурсивный вызов
    }

    static void Main()
    {
        Console.WriteLine(Factorial(5)); // Вывод: 120
    }
}

Проблемы и ограничения рекурсии

Переполнение стека

Если рекурсивные вызовы слишком глубоки, может возникнуть StackOverflowException.

Пример бесконечной рекурсии:

void InfiniteRecursion()
{
    InfiniteRecursion();
}

Оптимизация хвостовой рекурсии

Некоторые компиляторы оптимизируют хвостовую рекурсию, но в .NET такой оптимизации нет. В таких случаях лучше использовать циклы.

Переписывание факториала с помощью цикла:

int FactorialIterative(int n)
{
    int result = 1;
    for (int i = 2; i <= n; i++)
    {
        result *= i;
    }
    return result;
}

Когда использовать рекурсию

  • Обход сложных структур данных (деревья, графы).
  • Разбиение задач на более мелкие части (быстрая сортировка, поиск пути в лабиринте).
  • Вычисления, имеющие естественную рекурсивную природу (Фибоначчи, факториал).

Больше записей