Рекурсія

Рекурсія – конструкція, в якій метод напряму(пряма рекурсія) або через інші методи(складна рекурсія) викликає себе. Кількість вкладених викликів методу називають глибиною рекурсії. Рекурсивні методи дають можливість створювати повторювані обчислення без використання циклічних структур.

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

В математиці існує велика кількість рекурсивних функцій, які для обчислень використовують звертання до самих себе, тільки з іншими аргументами.

Такі функції поділяються на:

  • Скінченна рекурсивна функція – виконується за скінченну кількість рекурсивних викликів, які приводять до базового варіанту. Прикладом такої функції є факторіал числа, в якому для аргументу зі значенням 0, задано базовий варіант значення – 0! = 1;
  • Безкінечні рекурсивні функції – для таких функцій не існує базового варіанту і вони завжди викликають самі себе. Прикладом може слугувати безперервний дріб f(x) = x / (f(x+2))

При використанні рекурсивних функцій в програмуванні обов’язково задають базовий варіант, який призводить до припинення рекурсивних викликів і поверненню значення.

Факторіал числа

Факторіал числа n – це функція, яка повертає добуток всіх натуральних чисел від 1 до n включно. Для позначення факторіала використовується знак оклику - “!”, при цьому 0! = 1, n! = n ⋅ (n-1)!.

Функцію можна записати так:

  • f(0) = 1;
  • f(n) = f(n-1) ⋅ n.

Програма для рекурсивного обчислення факторіалу числа:

using System;

class Program
{
    static ulong Factorial(uint n)
    {
        return n == 0 ? 1 : Factorial(n - 1) * n;
        
        /* якщо не використовувати тернарний оператор, отримаємо:
        if (n == 0)
        {
            return 1;
        }
        else
        {
            return Factorial(n - 1) * n;
        }
        */
    }

    static void Main(string[] args)
    {
        Console.Write("n = ");
        var n = Convert.ToUInt32(Console.ReadLine());
        Console.WriteLine($"Факторіал числа {n} рівний {Factorial(n)}");
        Console.ReadLine();
    }
}

Розглянемо як це працює. До прикладу нам потрібно обчислити факторіал числа 3. Ми передаємо 3 в якості аргументу методу, і отримуємо наступний ланцюжок рекурсивних викликів:

Factorial(3) => Factorial(2) * 3 => Factorial(1) * 2 * 3 => Factorial(0) * 1 * 2 * 3 => 1 * 1 * 2 * 3 = 6.

Такий алгоритм обчислення факторіала має дві переваги:

  1. Мінімальна кількість коду;
  2. Повна відповідність математичному визначенню.

До недоліків можна віднести ресурси, що використовуються на рекурсивний виклик методу.

Обчислення факторіалу без використання рекурсії

Факторіал такох можна обчислити ітераційним, або циклічним методом:

static ulong Factorial(uint n)
{
    ulong result = 1;
    for (uint i = 1; i <= n; i++)
    {
        result *= i;
    }

    return result;
}

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

Числа Фібоначчі – це значення числової послідовності, в якій перші два члени рівні одиниці, а кожний наступний елемент рівний сумі двох попередніх чисел.

Послідовність із десяти перших членів ряду Фібоначчі має вигляд:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Математично послідовність можна записати так:

  • fib0 = 1
  • fib1 = 1
  • fibn = fibn-1 + fibn-2

Програма рекурсивного обчислення і виводу N перших членів послідовності Фібоначчі

using System;

class Program
{
    static uint FibonacciNum(uint n)
    {
        return (n == 0 || n == 1)
            ? 1 
            : FibonacciNum(n - 1) + FibonacciNum(n - 2);

        /*те саме без використання тернарного оператора
        if (n == 0 || n == 1)
        {
            return 1;
        }

        return FibonacciNum(n - 1) + FibonacciNum(n - 2);
         */
    }

    static void Main(string[] args)
    {
        Console.Write("N = ");
        var n = Convert.ToUInt32(Console.ReadLine());
        Console.WriteLine($"{n} перших чисел Фібоначчі");
        for (uint i = 0; i < n; i++)
        {
            var separator = i + 1 == n ? string.Empty : ", ";
            Console.Write($"{FibonacciNum(i)}{separator}");
        }
        Console.ReadLine();
    }
}

Рекурсивний метод має ті ж переваги, що і у випадку з факторіалом:

  1. Короткий код;
  2. Відповідає математичній формі запису.

Але в даному випадку є недолік, який суттєво впливає на швидкість обчислення кожного члену послідовності.

розглянемо дерево викликів рекурсивного методу для числа 5:

Як можна бачити, для деяких значень(в даному прикладі для 2 і 3) обчислення повторюються, що негативно впливає на швидкість обчислень.

Ітераційний метод

Для покращення швидкодії, перепишемо метод для обчислення чисел Фібоначчі з використанням циклу:

static uint FibonacciNum(uint n)
{
    uint nm1 = 1; //fib(n-1)
    uint nm2 = 1; //fib(n-2)
    uint result = 1;

    for (int i = 2; i <= n; i++)
    {
        result = nm1 + nm2;
        nm2 = nm1;
        nm1 = result;
    }

    return result;
}

Такох можна відразу отримати послідовність від 1-го до n-го члену в формі масиву:

using System;

class Program
{
    static uint[] FibonacciNumbers(uint n)
    {
        uint[] arr = new uint[n];
        n -= 1;
        if (n == 0)
        {
            arr[0] = 1;
        }
        else
        {
            arr[0] = 1;
            arr[1] = 1;
        }

        for (int i = 2; i <= n; i++)
        {
            arr[i] = arr[i - 1] + arr[i - 2];
        }

        return arr;
    }

    static void Main(string[] args)
    {
        Console.Write("N = ");
        var n = Convert.ToUInt32(Console.ReadLine());
        Console.WriteLine($"{n} перших чисел послідовності Фібоначчі");
        Console.WriteLine(string.Join(", ", FibonacciNumbers(n)));
        Console.ReadLine();
    }
}

Як видно з прикладів, рекурсивні методи, хоч і мають красивий вигляд і короткий код, не завжди ефективні. Крім цього велика глибина рекурсії може призводити до помилки переповнення стеку.

 Вправи

Дивіться також: