Учебное пособие по рекурсии

Question

Я изучаю Java из книги и встречаю главу о рекурсии с использованием факториала.

//A simple example of recursion 

package tutorials; 

class Factorial { 
// this is a recursive method 
int fact (int n) { 
    int result; 

    if(n==1) return 1; 
    result = fact(n - 1) * n; 
    return result; 
    } 
} 

class Recursion { 
    public static void main(String args[]) { 
     Factorial f = new Factorial(); 

     System.out.println("Factorial of 3 is " + f.fact(3)); 
     System.out.println("Factorial of 4 is " + f.fact(4)); 
     System.out.println("Factorial of 5 is " + f.fact(5)); 
    } 
} 

В результате этот кусок кода дает это «Факториал 3 является 6» и «Факториал 4 равен 24»

Что я не понимаю, что происходит в классе Факториал и почему * n не рассчитывается немедленно. Книга не очень хорошо объясняет это, поэтому я подумал, что я попрошу помочь опытным программистам.

Answer 1

Если вы вызываете fact(5), вот как это будет работать:

fact(5) 
    5*fact(4) 
     4*fact(3) 
      3*fact(2) 
       2*fact(1) 
        2*1=2 //(since if n==1, 1 is returned directly 
       result=2 
      result=3*2 
     result=4*3*2 
    result=5*4*3*2 
result=120 

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

Answer 2

Факториал числа n определяется как: n * (n - 1) * (n - 2) * ... * 1, что означает умножение n на целые положительные числа, меньшие n. В этом примере это просто обратное, поэтому вы сначала вычисляете факториал n-1, а затем умножаете его на n. Продолжая эту рекурсию, вы вычисляете факториал n - 2, n - 3 и т. Д., Пока вам не придется вычислять факториал 1. В этом случае вы просто возвращаете 1 себя и возвращаетесь в цепь рекурсии, вычисляя факториалы для 2, 3, ... n - 1, n.