Перейти до основного вмісту

Рекурсивні функції

Розглянемо рекурсивні функції окремо. Рекурсивна функція — це конструкція, в якій функція викликає сама себе.

Рекурсивна функція факторіалу​

Наприклад, візьмемо обчислення факторіалу, що використовує формулу n! = 1 * 2 * ... * n. Тобто, по суті, щоб знайти факторіал числа, ми перемножуємо всі числа до цього числа. Наприклад, факторіал числа 4 дорівнює 24 = 1 * 2 * 3 * 4, а факторіал числа 5 дорівнює 120 = 1 * 2 * 3 * 4 * 5.

Визначимо метод для знаходження факторіалу:

int Factorial(int n)
{
    if (n == 1) return 1;

    return n * Factorial(n - 1);
}

При створенні рекурсивної функції вона обов'язково повинна містити деякий базовий випадок, з якого функція починає обчислення. У випадку факторіалу це факторіал числа 1, який дорівнює 1. Факторіали всіх інших додатних чисел починаються з обчислення факторіалу числа 1, який дорівнює 1.

На рівні мови програмування для повернення базового випадку використовується оператор return:

if (n == 1) return 1;

Тобто, якщо вхідне число дорівнює 1, то повертається 1.

Інша особливість рекурсивних функцій: усі рекурсивні виклики повинні посилатися на підфункції, які зрештою зводяться до базового випадку:

return n * Factorial(n - 1);

Таким чином, якщо передати функції число, яке не дорівнює 1, подальші рекурсивні виклики підфункцій будуть кожного разу передавати число, менше на одиницю. Зрештою ми дійдемо до ситуації, коли число дорівнює 1, і буде використано базовий випадок. Це так званий рекурсивний спуск.

Використаємо цю функцію:

int Factorial(int n)
{
    if (n == 1) return 1;

    return n * Factorial(n - 1);
}

int factorial4 = Factorial(4); // 24
int factorial5 = Factorial(5); // 120
int factorial6 = Factorial(6); // 720

Console.WriteLine($“Factorial of the number 4 = {factorial4}”);
Console.WriteLine($“Factorial of number 5 = {factorial5}”);
Console.WriteLine($“Factorial of number 6 = {factorial6}”);

Розглянемо поетапно, що відбувається при виклику Factorial(4).

  1. Спочатку перевіряємо, чи число дорівнює одиниці:
if (n == 1) return 1;

Але спочатку n дорівнює 4, тому ця умова хибна, і відповідно виконується код

return n * Factorial(n - 1);

Тож фактично маємо:

return 4 * Factorial(3);
  1. Далі виконується вираз:
Factorial(3)

Знову ж, n не дорівнює 1, тому виконується код

return n * Factorial(n - 1);

Тож фактично:

return 3 * Factorial(2);
  1. Далі виконується вираз:
Factorial(2)

Знову ж, n не дорівнює 1, тому виконується код

return n * Factorial(n - 1);

Тож фактично:

return 2 * Factorial(1);
  1. Далі виконується вираз:
Factorial(1)

Тепер n дорівнює 1, тому виконується код

if (n == 1) return 1;

І повертається 1.

Нарешті, вираз

Factorial(4)

На практиці, це виявляється

4 * 3 * 2 * Factorial(1).

Рекурсивна функція Фібоначчі​

Іншим поширеним ілюстративним прикладом рекурсивної функції є функція, яка обчислює числа Фібоначчі. n-й член послідовності Фібоначчі визначається за формулою: f(n)=f(n-1) + f(n-2), при f(0)=0 і f(1)=1. Тобто, послідовність Фібоначчі виглядатиме так: 0 (0-й член), 1 (1-й член), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ..... Для визначення чисел цієї послідовності, визначимо наступний метод:

int Fibonachi(int n)
{
    if (n == 0 || n == 1) return n;
    
    return Fibonachi(n - 1) + Fibonachi(n - 2);
}

int fib4 = Fibonachi(4);
int fib5 = Fibonachi(5);
int fib6 = Fibonachi(6);

Console.WriteLine($“4 Fibonacci number = {fib4}”);
Console.WriteLine($“5 Fibonacci number = {fib5}”);
Console.WriteLine($“6 Fibonacci number = {fib6}”);

Тут базовий випадок виглядає наступним чином:

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

Тобто, якщо ми шукаємо нульовий або перший елемент послідовності, повертається те ж саме число, 0 або 1. В іншому випадку повертається результат виразу Fibonachi(n - 1) + Fibonachi(n - 2);

Рекурсії та цикли​

Це найпростіші приклади рекурсивних функцій, які покликані дати розуміння того, як працює рекурсія. Однак для обох функцій можна використовувати циклічні конструкції замість рекурсій. І зазвичай, альтернативи на основі циклів є швидшими та ефективнішими за рекурсію. Наприклад, обчислення чисел Фібоначчі за допомогою циклів:

static int Fibonachi2(int n)
{
	int result = 0;
	int b = 1;
	int tmp;

	for (int i = 0; i < n; i++)
	{
		tmp = result;
		result = b;
		b += tmp;
	}

	return result;
}

У той же час, рекурсія надає елегантне рішення в деяких ситуаціях, таких як обхід різних деревоподібних структур, наприклад, дерева каталогів та файлів.