Rekursja w Javie Jak to działa?

Question

Proszę wyjaśnić działanie instrukcji rekursji w poniższym kodzie.

int factR(int n) { 
    int result; 

    if(n==1) return 1; 

    result = factR(n-1) * n; 
    return result; 
} 

Moje zrozumienie jest, że:

W powyższym stwierdzeniem metoda factR(n-1) nazywa się aż do końca. Załóżmy, że chcemy uzyskać silnię z 6, która zostanie wysłana do tej metody jako argument. Zostanie odebrany jako parametr n, a następnie zostanie sprawdzona wartość n; jeśli jest 1, to zostanie zwrócone 1. Ale jeśli nie jest 1, tak jak w naszym przypadku, gdzie jest 6, wtedy instrukcja rekursji będzie działać.

Problem polega na tym, że po raz pierwszy n-1 staje się 5 i jest mnożony przez n, który przechowuje wartość 6, następnie staje się 30. Teraz gdzie to będzie 30 GO?

Następnie metoda wywoła samą siebie i tym razem n-1 staje się 4, a następnie mnoży się z n, która IF ma wartość "6", a następnie 4 * 6 = 24, co moim zdaniem jest błędne. Ponieważ jeśli przejdziemy tą drogą, to w następnym wywołaniu proces będzie podobny, n-1 stanie się 3 * n, który JEŻELI będzie miał taką samą wartość, tj. 6, wtedy stanie się 3 * 6 = 18. Wtedy pojawi się następne połączenie i n-1 staje się 2, jeśli pomnożymy i przypuśćmy, że n ma wartość 6, a następnie 2 * 6 = 12, a na końcu wywołanie n-1 = 1 * n = 6. Mój punkt jest taki, że jest jasne, że n-1 zmniejszy wartość n-1, tj. 6-1 = 5, następnie 5-1 = 4, następnie 4-1 = 3, następnie 3-1 = 2 i 2-1 = 1. ALE pytanie brzmi, jaka będzie wartość n, która będzie mnożona za każdym razem, gdy sama metoda wywoła?

Jeśli powiesz, że gdy pojawi się pierwsze mnożenie, tj. "N-1" stanie się 5, pomnożone przez 6 = 30, a 30 zostanie zapisane w "n", a następnie w następnym wywołaniu 5-1 = 4 * 30 = 120 , następnie 4-1 = 3 * 120 = 360, następnie 3-1 = 2 * 360 = 720, a na końcu 1 * 720 = 720, to w jaki sposób Java określa, aby umieścić wynikową wartość z powrotem w zmiennej n?

Gdybym miejsce innego komunikatu, by sprawdzić jaka jest wartość zmiennej result każdym razem metoda nazywać się w ten sposób, jak to:

int factR(int n) { 
    int result; 

    if(n==1) return 1; 

    result = factR(n-1)*n ; 
    System.out.println(result); 
    return result; 
} 

Potem dostać wyjście:

2 
6 
24 
120 
720 
Factorial of 6 is 720 

Nie rozumiem, jak produkuje 2 w pierwszym wywołaniu. Skąd bierze się wartość 2, a następnie 6, 24, 120 i 720? Myślę, że poważnie utknąłem w działaniu kodu.

Answer 1

Metoda powinna być naprawdę skonstruowany tak, aby znaleźć silni n:

int factorial(int n) 
{ 
    if (n == 1) 
     return 1; 

    return n * factorial(n - 1); 
} 

nie jest to bardzo dobry pomysł, moim zdaniem do wystąpienia nowych zmiennych wewnątrz funkcji rekurencyjnej, ponieważ” Będą po prostu resetowane przy każdym wywołaniu z powodu zasięgu.

Answer 2

To, czego możesz tu nie zauważyć, to to, że n jest zmienną lokalną dla twojej funkcji. Oznacza to, że każde wywołanie funkcji (może przez rekursję lub nie) otrzymuje nową zmienną n, która zawiera parametr tej funkcji. Ponieważ jest to typ wartości, jest kopiowany, a nie odwołanie do pierwotnej wartości. Dlatego wszelkie zmiany w jednym wywołaniu nie wpływają na zmienne w innych (rekurencyjnych) wywołaniach.

W rezultacie funkcja najpierw otrzymuje kopię 6 i zmniejsza ją o 1 jako kopię do następnego wywołania funkcji. To wywołanie otrzymuje "kopię" 6-1=5 i zmniejsza ją ponownie - i tak dalej. Po osiągnięciu 1 zwraca również 1. Następnie ponownie przechodzi przez stos wywołań i mnoży wynik ostatniego połączenia z lokalną zmienną w tym wywołaniu. Tak więc 1 zostaje pomnożony przez 2 i zostaje zwrócony. Wynik ten zostanie pomnożony przez 3 i tak dalej. W końcu skończysz z silnią.

Answer 3

Funkcja rozwija się, dopóki nie zostanie osiągnięte oświadczenie o zakończeniu (n == 1). Załóżmy, że n = 6, mamy factR(n-1) * n = factR(5) * 6, ale co to jest factR(5)? Cóż, to tylko factR(4) * 5, a więc widzimy, że factR(5) * 6 = (factR(4) * 5) * 6. Teraz pamiętać, że factR(1) = 1 i otrzymujemy

factR(6) = factR(5) * 6 
     = (factR(4) * 5) * 6 
     = ((factR(3) * 4) * 5) * 6 
     = (((factR(2) * 3) * 4) * 5) * 6 
     = ((((factR(1) * 2) * 3) * 4) * 5) * 6 
     = ((((1 * 2) * 3) * 4) * 5) * 6 
     = (((2 * 3) * 4) * 5) * 6 
     = ((6 * 4) * 5) * 6 
     = (24 * 5) * 6 
     = 120 * 6 
     = 720 

Answer 4

w Javie, mamy coś, co nazywa się stos.

Za każdym razem, gdy metoda zostanie wywołana inną metodą, zostanie ona dodana do stosu.

________ 
|factR(1)| = <prints nothing> 
________ 
|factR(2)| = 2 
________ 
|factR(3)| = 6 
________ 
|factR(4)| = 24 
________ 
|factR(5)| = 120 
________ 
|factR(6)| = 720 

to w zasadzie oznacza, że ​​dla metody factR(6) aby zakończyć, factR(5) musi wypełnić, aby zakończyć na factR(5), factR(4) musi wypełnić i tak dalej.

Zadzwoń pod numer , a następnie zaczekaj na zakończenie, ponieważ wynik zależy od tego.

Ale, w factR(5), ty również wykonujesz wywołanie rekurencyjne i musisz poczekać.

I tak dalej, aż trafiliśmy limitu factR(1), który będzie po prostu wrócić 1.

Z factR(1) zakończeniu factR(2) można następnie wydrukować wynik i zwraca wynik do sposobu jego macierzystej, i tak dalej, aż do factR(6) drukuje i zwraca wyniki