Интерактивен учебник по информатика

Какво е рекурсия

Рекурсията е метод, който вика сам себе си. Звучи странно — как нещо да работи, ако в средата на работата си стартира ново копие от себе си? Тайната е, че всяко следващо извикване работи върху по-малък вход, докато стигне до тривиален случай, който може да реши директно.

Класически пример — факториел

Факториелът се дефинира така:

0! = 1 ← база
n! = n · (n−1)! ← индуктивен случай

В код:

static long Factorial(int n)
{
    if (n <= 1) return 1;          // база
    return n * Factorial(n - 1);   // индуктивен случай
}

Console.WriteLine(Factorial(5));   // 120

Стек на извикванията

Когато Factorial(4) извика Factorial(3), текущото му състояние се запазва в стек на извикванията (call stack). Всяко ниво чака долното да върне резултат:

Фиг. 1 — Стекът на извикванията расте надолу, после се връща нагоре

Още класически примери

Сума на числата от 1 до n

static int Sum(int n)
{
    if (n == 0) return 0;          // база
    return n + Sum(n - 1);         // индуктивен случай
}

Console.WriteLine(Sum(100));   // 5050

Степенуване — x на n-та

static double Power(double x, int n)
{
    if (n == 0) return 1;
    return x * Power(x, n - 1);
}

Console.WriteLine(Power(2, 10));   // 1024

Числата на Фибоначи

F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2):

static long Fibonacci(int n)
{
    if (n < 2) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Console.WriteLine(Fibonacci(10));   // 55

Двоично търсене (рекурсивно)

В сортиран масив — гледаме средния елемент. Ако е по-голям от търсеното — търсим в лявата половина; ако е по-малък — в дясната.

static int BinarySearch(int[] arr, int target, int left, int right)
{
    if (left > right) return -1;       // база — не намерено
    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target)
        return BinarySearch(arr, target, left, mid - 1);
    else
        return BinarySearch(arr, target, mid + 1, right);
}

int[] arr = { 1, 3, 5, 7, 9, 11, 13, 15 };
Console.WriteLine(BinarySearch(arr, 11, 0, arr.Length - 1));   // 5

Рекурсия vs цикъл

Почти всяка рекурсия може да се напише и с цикъл (и обратното). Кога кое?

	Рекурсия	Цикъл (итерация)
Четимост	Често по-кратка и близка до математическата дефиниция	По-многословна, но „по-механична"
Памет	Заема място в стека на извикванията	Минимална — само локални променливи
Скорост	По-бавна (има overhead от извикването)	Малко по-бърза
Дълбочина	Ограничена от размера на стека (≈ 10 000 нива)	Неограничена
Подходяща за	Дървовидни структури, разделяй и владей, графи	Прости повторения, обхождане на масиви

Иterative variant of factorial

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

За факториел итеративният вариант е и по-кратък, и по-бърз, и не рискува препълване на стека. За много задачи обаче рекурсията се чете много по-естествено.

Често срещани грешки

Липсваща база — рекурсията не спира и хвърля StackOverflowException.
Грешна база — спира, но връща грешен резултат. Пример: if (n == 0) return 0; за факториел вместо return 1.
Не намалява входа — return Factorial(n); вместо Factorial(n - 1) също дава безкрайна рекурсия.
Дублирани изчисления — както при Фибоначи; решава се с мемоизация или преобразуване в цикъл.

Какво трябва да запомниш

Рекурсия = метод, който вика себе си с по-малък вход.
Винаги има база (спира) и индуктивен случай (продължава).
Извикванията се пазят в стека → твърде дълбоко = stack overflow.
Кога рекурсия: естествено рекурсивни задачи (дървета, графи, разделяй и владей).
Кога цикъл: прости повторения, чести и дълбоки рекурсии, приоритет към скорост.
Шаблон: if (база) return известната-стойност; return нещо(вика-се-с-по-малък-вход);