Основы рекурсии

Question

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

Вот источники рекурсии:

• Рекурсия в Java
• Рекурсия 3

У меня есть одна вещь, которую нужно спросить, так как в коде я видел одну вещь, которая является if-else.Я знаю, если еще условие очень хорошо.Но здесь все немного сложнее.

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

В приведенном выше коде здесь результат выглядит верным, но почему-то я думаю, почему он не возвращает только 1, когда удовлетворяет условию, и почему он печатает правильный результат.Есть один улов, который я не смог уловить.Пожалуйста, помогите мне пройти через это.

Считайте меня учеником в области кодирования.Спасибо

Answer 1

Рекурсивная функция - это функция, которую вызывает сама по себе

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

Недостатком является то, что они могут вызывать бесконечные циклы и другие неожиданные результаты, если записано неправильно .

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

1. Первое, что нужно рассмотреть, это когда вы решите выйти из цикла, который является циклом if

2. Второй процесс, который нужно выполнить, если мы являемся нашей собственной функцией

Из данного примера:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

Из примера выше

if(n <=1)
     return 1;

Является решающим фактором при выходе из цикла

else 
     return n * fact(n-1);

Является ли фактическая обработка, которая должна быть сделана

Позвольте мне разбить задачу по одному длялегкое понимание.

Давайте посмотрим, что произойдет внутри, если я запусту fact(4)

1. Подставляя n = 4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

*Сбой цикла 1053 *If переходит на цикл else с возвратом 4 * fact(3)

В стековой памяти у нас есть 4 * fact(3)

Подставляя n = 3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If циклпроисходит сбой, поэтому он переходит к else loop

, поэтому он возвращает 3 * fact(2)

Помните, что мы назвали `` `4 * fact (3)` `

Выход дляfact(3) = 3 * fact(2)

Пока в стеке 4 * fact(3) = 4 * 3 * fact(2)

В стековой памяти у нас есть 4 * 3 * fact(2)

Подставляя n = 2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If циклпроисходит сбой, поэтому он переходит к else loop

, поэтому он возвращает 2 * fact(1)

Помните, что мы вызвали 4 * 3 * fact(2)

Выход для fact(2) = 2 * fact(1)

Пока стек имеет 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

В стековой памяти мы имеем 4 * 3 * 2 * fact(1)

Подставляя n = 1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If циклtrue

, поэтому он возвращает 1

Помните, что мы назвали 4 * 3 * 2 * fact(1)

Вывод для fact(1) = 1

Пока стек имеет 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Результат факт (4) = 4 * 3 * 2 * 1 = 24

Answer 2

Alok, допустим, вы пропустили 3 и теперь первая итерация ждет результата от вызова функции.Теперь этот вызов запускает другой вызов и ждет повторного вызова.Наконец, когда он равен 1, возвращает 1, и этот вызов имеет ответ, и поэтому он умножается и отправляет результат обратно.Таким образом, return в конце концов достигает первого звонка, который ожидает, и возвращается окончательный ответ.Проще всего вы позвонили человеку (а), и этот человек позвал другого человека (б), а тот человек позвонил другому (в), который дал ему ответ.Теперь, когда c дал ответ, b обрабатывает этот ответ и передает его тем, кто, в свою очередь, обрабатывает этот ответ и возвращает его вам.По этой причине вы получили правильный ответ вместо 1 в рекурсивной программе.Надеюсь, вы поняли это.

Спасибо Vino V

Answer 3

Просмотр рекурсивной функции в виде дерева значительно облегчает понимание новичкам.Каждая рекурсивная функция работает в два этапа:

Шаг 1 : расширение дерева

Шаг 2 : обратное замещение

Рассмотримизображение ниже.На изображении красный цвет показывает шаг 1, а зеленый цвет показывает шаг 2. Вы не можете выполнить шаг 2, пока шаг 1 не завершится.По этой причине вам необходимо иметь условие завершения в каждой рекурсивной функции;дерево будет продолжать расширяться, вашей программе не хватит памяти.

Когда вы вызываете fact(4), оно расширяется как 4 * fact(3), что далеерасширен, как показано ниже:

fact(4) = 4 * fact(3)
fact(3) = 3 * fact(2)
fact(2) = 2 * fact(1)
fact(1) = 1

Теперь все, что вам нужно сделать, - это заменить значения обратно, чтобы получить значение fact(4).

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

Answer 4

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

Так <= 1 является одним условием исключенияэто нужно было обрабатывать отдельно, а затем нарушать дальнейшие вычисления.</p>

По этой причине условие дескриптора предложения <= 1 и предложение else вызывают один и тот же метод факта для вычисления факториала n-1.Посмотрите на комментарии в коде ниже. </p>

public static int fact(int n) {
    if (n <= 1) {
        // if a number is 1 or less than on then factorial will be 1
        return 1;
    } 
    else {
        /*this part will execute only of number is greater than 1, ex 2,3
         * According to factorial logic, factorial of a number n will be (n * factorial of (n-1))
         * Ex: factorial of 2 = 2*1
         *  factorial of 3 = 3*2*1
         *  factorial of 4 = 4*3*2*1
        */
        return n * fact(n - 1);
    }
}

Answer 5

Я думаю, что лучший способ понять это на примере.Например, если вы вызываете fact (3), код выполнения будет выглядеть следующим образом (как псевдокод):

fact (3)

3 is greater than 1 so
return 3 * fact(2)  ---> Lets wait for this

fact (2)

2 is greater than 1 so
return 2 * fact(1)  ---> Lets wait for this

факт (1)

1 is same as 1 so
return 1 ---> 1 will be the result of fact(1)

Теперь вернемся к факту (2)

return 2 * 1 --> 2 this will be the result of fact(2)

Теперь вернемся к факту (3)

return 3 * 2 ---> This give 6, and it is the final result of fact(3)

Answer 6

Привет, коллега, изучающий код, я надеюсь, что люди в StackOverflow пощадят ваш вопрос, потому что они никогда не обращали внимания на мои вопросы.

В любом случае, давайте пробежимся по вашему коду и посмотрим, что именно происходит:

я собираюсь назвать "факт (5)" в моей главной.Ниже приводится представление о том, что происходит в фоновом режиме:

public static int fact(5){
  if(5 <=1)
     return 1;
  else 
     return 5 * fact(4);
}

и факт 4 будет:

public static int fact(4){
  if(4 <= 1)
     return 1;
  else 
     return 4 * fact(3);
}

и т. Д .:

public static int fact(3){
  if(3 <= 1)
     return 1;
  else 
     return 3 * fact(2);
}

public static int fact(2){
  if(2 <= 1)
     return 1;
  else 
     return 2 * fact(1);
}

public static int fact(1){
  if(1 <= 1) //true for the first time
     return 1;
  else 
     return 1 * fact(0);
}

в "fact (1)" случай if запускается впервые и возвращает 1. Если мы сейчас вернемся вверх:

//fact(1) = 1
public static int fact(2){ //returns the else case, 2*1 = 2 so fact(2) = 2
  if(2 <= 1)
     return 1;
  else 
     return 2 * 1;
}

public static int fact(3){ //same here, fact(2) = 2, so we end up with 3*2 = 6
  if(3 <= 1)
     return 1;
  else 
     return 3 * 2;
}

public static int fact(4){
  if(4 <= 1)
     return 1;
  else 
     return 4 * 6; //fact(3) = 6, so we return 4*6 = 24
}

public static int fact(5){
  if(5 <= 1)
     return 1;
  else 
     return 5 * 24; //fact(4) = 24, so we return 5*24 = 120
}

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

Answer 7

Простой пробный прогон приведет вас к вашему ответу.N каждый раз вычитается по одному, пока не достигнет 1.

Например, давайте рассмотрим N как 4

. Это будет сделано в операторе else, который станет return 4 * fact(4-1)

* 1007.* Рекурсия теперь имеет 4 * fact(3)

факт 3 приведет к 3 * fact (2)

, что приравнивает первое уравнение к 4 * 3 * fact(2);

Это происходитпока N не станет 1, значит, все уравнение будет выглядеть как 4 * 3 * 2 * 1

в 1, рекурсия останавливается, и мы начинаем возвращаться через стек рекурсии.

Надеюсь, это прояснит ваш вопрос.