Реализуйте факториал в коде

Рекурсия - это когда метод вызывает сам себя. Когда метод ведет себя подобным образом, он называется рекурсивным методом.

Рекурсия довольно часто используется в математике при работе с рекурсивными последовательностями. Если вы не знакомы с рекурсивными последовательностями, это просто когда следующие термины в последовательности используют предыдущие термины. Я уверен, что некоторым из вас могут прийти в голову факториал или рекурсивные последовательности Фибоначчи.

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

Если вы внимательно посмотрите на подсолнух, он выглядит как круги внутри других кругов. Однако, поскольку это связано с развитием, я постараюсь не слишком увлекаться природой. Я реализую факториальную последовательность с помощью типичного цикла for, а затем сделаю это рекурсивно.

Факториал

Факториал - это произведение целого числа и всех целых чисел под ним. An! используется для его обозначения. Например, 1 x 2 x 3 x 4 x 5 можно записать как 5 !. 0! = 1. Это может быть реализовано как простой цикл и предполагает использование только положительных целых чисел.

public static int factorial(int number){
    if ( number <= 1){
        return 1;
    }
    int sum = 1;
    for(int i = 2; i < number + 1; i ++ ){
        sum *= i;
    }
    return sum;
}

Если вы вызовете этот метод с 5, вы получите 120.

Рецидивирующая зависимость

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

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

0! => 1
1! => 1 => 1x1 => 1x0!
2! => 2x1 => 2x1!
3! => 3x2x1 => 3x2!
4! => 4x3x2x1 => 4x3!
5! => 5x4x3x2x1 => 5x4!
6! => 6x5x4x3x2x1 => 6x5!

На этом этапе мы видим, что рекуррентная зависимость начинается с 2.

1 и 0 являются частными случаями, и оба равны 1.

6! = 6x5! также можно записать как 6x (6–1) !. Если мы заменим константу на n, мы получим n (n -1) !.

Давайте воспользуемся этим, чтобы рекурсивно реализовать ту же функцию.

public static int factorial(int number){
    if ( number <= 1){
        return 1;
    }
    return number * factorial(number -1);
}

Условие if обрабатывает два особых случая. 1 возвращается для всего, что равно или меньше 1.

Помните, что для цикла всегда требуется условие прорыва. Повторяющаяся зависимость начинается с 2, поэтому, когда числовое значение достигает 1, метод перестанет вызывать сам себя.

Заключение

Поначалу может быть сложно понять рекурсию, но на самом деле все очень просто.

На это нужно смотреть так же, как на петлю. Единственная разница в том, что почти всегда есть какие-то особые случаи до того, как начинает появляться повторяющаяся зависимость. Эти случаи будут вашим условием прорыва, а ваша формула - это то, что используется для рекурсивного вызова вашего метода, как мы видели в предыдущем примере.