Как понять концепцию рекурсии в java?

Рекурсивная функция — это функция, которая вызывает себя до тех пор, пока не достигнет оператора return, который не позволяет ей вызвать себя. Возьмем, к примеру, функцию факториала. Факториал — это математическая функция, которая возвращает число, умноженное само на себя — 1 умноженное само на себя — 2, ... умноженное на 1, пример: факториал 5 = 5! = 5x4x3x2x1 = 120. оно также равно самому себе, умноженному на факториал самого себя -1, что равно: 5! = 5х4! Учтите, что 0! = 1. чтобы представить это в коде Java, вам нужен цикл, который умножает числа, начиная с 1, и до числа, которое вы вычисляете для своего факториала. Более того, объясняя ваш код, давайте вычислим Factorial(5): Factorial() возвращает целое число.

Начальный вызов из main(): 5 != 0, затем пропустить условие (n == 0); т = факториал (5-1) = факториал (4);

Второй вызов из Factorial(4): 4 != 0, затем пропустить условие (n == 0); т = факториал (4-1) = факториал (3);

Третий вызов из Factorial(3): 3 != 0, затем пропустить условие (n == 0); т = факториал (3-1) = факториал (2);

Четвертый вызов из Factorial(2): 2 != 0, затем пропустить условие (n == 0); т = факториал (2-1) = факториал (1);

Пятый вызов из Factorial(1): 1 != 0, затем пропустить условие (n == 0); т = факториал (1-1) = факториал (0);

Шестой вызов Factorial(0): 0 == 0, затем возвращает значение 1;

Первый возврат, 1, к Пятому вызову (Factorial(1)): return n*t = return 1*1 = возвращаемое значение 1;

Второй возврат, 1, к четвертому вызову (Factorial(2)): return n*t = return 2*1 = возвращаемое значение 2;

Третий возврат, 2, к третьему вызову (Factorial(3)): return n*t = return 3*2 = возвращаемое значение 6;

Второй возврат, 6, ко второму вызову (Factorial(4)): return n*t = return 4*6 = возвращаемое значение 24;

Второй возврат, 24, к первому вызову (Factorial(5)): return n*t = return 5*24 = возвращаемое значение 120;

Второй возврат, 120, к начальному вызову (из main()): print(120);

Надеюсь, это поможет вам понять рекурсию.

Когда выполняется вызов другого метода, создается кадр стека для хранения состояния текущего метода, и он помещается в стек. Это не зависит от того, вызывает ли метод себя или другой метод.

Когда вызов возвращается, кадр стека извлекается из стека, состояние метода восстанавливается, и выполнение продолжается в вызывающем методе.

Рекурсия — это когда метод (прямо или косвенно) вызывает сам себя. Общая форма рекурсивного метода:

• Если параметр соответствует условию завершения, возврат (обычно результат)
• В противном случае настройте параметры для следующей итерации и вызовите self

Код, написанный вашим учителем, имеет некоторые проблемы со стилем. Было бы понятнее, если бы было написано так:

static int factorial(int n) {
    if (n == 0) {
        return 1;
    } 
    return n * factorial(n - 1);
}

Искоренение ненужной переменной t и избыточной else (нет "иначе", когда возвращается "если" - есть просто продолжение выполнения)

Я бы написал это так, полностью исключив if:

static int factorial(int n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

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

Лично мне проблема факториала не нравится. Мне это трудно понять, и я не думаю, что это ясно объясняет рекурсию. Итак, давайте рассмотрим другой пример. Допустим, мы хотим напечатать числа от 1 до 100. Это очень простая задача с циклом for и счетчиком, но ее также можно выполнить с помощью рекурсии. Например:

public static void main(String[] args) {
    numbersAscending(1);
    numbersDescending(1);   
}
//Prints 1 2 3 ... 100
public void numbersAscending(int x){
    System.out.println(x);
    if(x < 100){
        numbersAscending(x+1);
    }
}
//Prints 100 99 98 ... 1
public void numbersDescending(int x){
    if(x < 100){
        numbersDescending(x+1);
    }
    System.out.println(x);
}

Когда вызывается функция, этот вызов помещается на вершину стека. Думайте об этом как о стопке карт. На каждом есть номер (1-100). Когда функция вызывает сама себя, в стек добавляется новая карта. Когда функция завершается, она удаляется из стека.

Таким образом, в приведенном выше примере каждый раз, когда вызывается numberAscending, он выводит текущее значение для x перед повторным вызовом этой функции. В результате числа печатаются в порядке от 1 до 100. Как только будет достигнуто значение 100, он перестанет вызывать сам себя и вытолкнет каждую функцию из стека.

С другой стороны, каждый раз, когда вызывается numberDescending, он снова вызывает сам себя, прежде чем распечатать номер. Таким образом, x не начинает печатать, пока не достигнет 100. Затем он перемещается обратно вниз по стеку, печатая каждое число по мере возвращения к основному методу.

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

n!=1*2*...*n

мы определяем

1!=1

и

n!=n*(n-1)!

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

по второму определению

5!=5*4!

но 4!=4*3! так что 5!=5*4*3!

но 3!=3*2! так что 5!=5*4*3*2!

и так далее. Продолжайте делать это, пока не нажмете 1!. Но 1!=1, так что вы останавливаетесь.

Рекурсия в программировании — то же самое.

ТомВ