Рекурсия

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

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

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

Существуют два вида функций:

  • Конечная рекурсивная функция – выполняется за конечное количество рекурсивных вызовов, которые приводят к частному или базовому варианту. Примером такой функции является факториал числа, в котором для аргумента со значением 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();
    }
}

Как видно из примеров, рекурсивные методы, хоть и имеют красивый вид и краткий код, не всегда эффективны. Кроме этого большая глубина рекурсии может приводить к ошибке переполнения стека.

 Упражнения

Смотрите также: