Алгоритми рекурсії не дуже популярні в продукційному коді. Головна причина — рекурсія має чимало обмежень. Але якщо вона вам потрібна, ви повинні чітко розуміти, як вона працює, та як уникнути можливих обмежень.
Рекурсія в C# — це метод, який викликає сам себе прямо або опосередковано для вирішення задачі. Це чітке визначення, але як розробник, чи впевнені ви, що розумієте, як це працює?
Давайте розглянемо класичний приклад реалізації рекурсії — обчислення факторіала.
Код виглядатиме ось так:
long Factorial(int n)
{
if (n == 0)
return 1;
return n * Factorial(n - 1);
}
У C# рекурсія залежить від стеку викликів для відстеження контексту кожного рекурсивного виклику.
Кожен виклик створює фрейм стека:
Кожного разу, коли метод викликає сам себе рекурсивно, стан методу (локальні змінні, параметри, адреса повернення) додається до стеку викликів.
Ви будете множити всі числа від N до 1 (коли N = 0, ми повернемо 1).
Для візуалізації можна використовувати вікно Call Stack у Visual Studio:
Вікно Call Stack у Visual Studio
Але приклад з факторіалом не зовсім наочно показує всю інформацію в стеці викликів, оскільки він занадто простий.
Розглянемо приклад функції IsEven:
bool IsEven(int x)
{
if (x == 0)
return true;
if (IsEven(x - 1))
{
return false;
}
else
{
return true;
}
}
Вікно Call Stack покаже таку інформацію, якщо ми перевіримо результат для X=7:
Вікно Call Stack у Visual Studio
Для X=0 ми завжди повертаємо true, оскільки це парне число.
Для інших кожен виклик залежатиме від наступного виклику в стеці викликів.
Діаграма виглядатиме ось так:
Діаграма для функції Is Even, коли X=7
Діаграма чітко показує, що кожен виклик методу використовує результат наступного виклику, щоб визначити наступний крок у отриманні результату.
У сценаріях, де використовується рекурсія, моніторинг глибини рекурсивних викликів може бути критично важливим, особливо для запобігання помилок переповнення стека або проблем із налагодженням. C# надає клас StackTrace, який дозволяє вам перевіряти поточний стек викликів. Цей клас можна використовувати для програмного відстеження і логування глибини рекурсії, що дає уявлення про потік виконання рекурсивних методів. Однак використовувати його слід обережно, оскільки надмірна перевірка стека може вплинути на продуктивність у випадках глибокої рекурсії.
Успіхів у програмуванні!
Перекладено з: Easiest explanation of recursion in C#