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

Я изучаю 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».

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


java recursion factorial
person Stephen Worrall    schedule 14.05.2015    source источник
comment
Потому что в компьютерных науках и программировании в целом вы хотите сэкономить как можно больше вычислений. выполнение рекурсивного * N нагружает систему. Поместить его в очередь и дождаться, пока рекурсия достигнет 1, — очень желательный метод.   -  person booky99    schedule 15.05.2015
comment
Этот вопрос programmers.stackexchange.com/ Questions/25052/ может быть хорошим местом для начала.   -  person Marc K    schedule 15.05.2015
comment
Держитесь подальше от рекурсии и используйте ее только в случае необходимости.   -  person Ritesh Karwa    schedule 15.05.2015
comment
Как себе это: Что такое факториал 5? Ответ прост: это факториал числа 4, умноженный на 5. Что такое факториал числа 4? Это в 4 раза больше факториала 3. (и т. д.)   -  person    schedule 15.05.2015
comment
@RiteshK, так что никто не должен утруждать себя изучением или попыткой понять это?   -  person ChiefTwoPencils    schedule 15.05.2015
comment
@ChiefTwoPencils, который сказал не учиться   -  person Ritesh Karwa    schedule 15.05.2015
comment
@ChiefTwoPencils, я сказал, используй его, только если сможешь справиться с этим.   -  person Ritesh Karwa    schedule 15.05.2015

Ответы (2)


arrow_upward
2
arrow_downward

Если вы вызываете 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). Внутри переменные помещаются в стек, чтобы их запоминали при каждом вызове, но это, вероятно, обсуждение в другой раз.

person kaykay    schedule 14.05.2015
comment
Хорошо, kaykay, я вроде как понял, я попытался повторно запустить программу, используя точки останова, и пройтись по ней, чтобы увидеть, что происходит с переменными, но все еще нахожу это раздражающе озадачивающим, но ваше объяснение помогло мне немного прояснить ситуацию. вода. Спасибо, - person Stephen Worrall; 15.05.2015

arrow_upward
-1
arrow_downward

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

person Iamsomeone    schedule 14.05.2015
comment
Серьезно, в этом ответе есть что-то плохое? - person Iamsomeone; 26.05.2015