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

Question

Я новичок в программировании на Java, и наш учитель научил нас концепции рекурсии, и я обнаружил, что это немного сложно. Все, что я понял, что это работает как цикл (например, факториал 4), но я все еще не совсем понимаю, почему он работает так. Могу ли я получить подробное объяснение по этой теме? Вот фрагмент кода и фотография, которую мой учитель объяснял.

package javaapplication1; 

public class JavaApplication1 { 

static int factorial(int n){ 
    int t; 
    if(n == 0){ 
     return 1; 
    } else { 
     t = factorial(n - 1); 
     return n * t; 
    } 
} 
public static void main(String[] args) { 
    System.out.println(factorial(5)); 
    } 
} 

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

http://i.stack.imgur.com/pjqJy.png

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

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

I бы написать это, устраняя if в целом:

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

Answer 4

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

п! = 1 * 2 * ... * п

из определим

1! = 1

и

п! = П * (п-1) !

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

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

5! = 5 * 4!

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

но 3! = 3 * 2! поэтому 5! = 5 * 4 * 3 * 2!

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

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

TomW

Answer 5

Лично мне не нравится факторная проблема. Мне трудно понять, и я не думаю, что это объясняет рекурсию ясным образом. Поэтому давайте рассмотрим другой пример. Допустим, что мы хотим печатать цифры от 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). Когда функция вызывает себя, в стек добавляется новая карта. Когда функция заканчивается, она снимается со стека.

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

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