Переменная-член все еще находится в буфере, когда рекурсивная функция получает вызов?

Question

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

вот мой код:

 public static int gcd(int m,int n)
{

    System.out.println("Entering 'gcd' method:  m= "+m+",  n="+n);
    if(m%n==0)
    {         
       System.out.println("Returning 'gcd' value ="+n+" (Base case:      m=)"+m+",  n="+n );    
        return n;
    }
    else          
    {

        int temp= gcd(n,m%n);
        System.out.println("Returning 'gcd' value ="+temp+" (recursive case:      m=)"+m+",  n="+n );

        return temp;

    }

Не знаюпонять, когда я ввожу 843 99 System.out.println, прежде чем вернуть темп.станет обратной печатью из M и N

, например:

enter two integers(or 'q' to exit):843 99
Entering 'gcd' method:  m= 843,  n=99
Entering 'gcd' method:  m= 99,  n=51
Entering 'gcd' method:  m= 51,  n=48
Entering 'gcd' method:  m= 48,  n=3
Returning 'gcd' value =3 (Base case:      m=)48,  n=3
Returning 'gcd' value =3 (recursive case:      m=)51,  n=48
Returning 'gcd' value =3 (recursive case:      m=)99,  n=51
Returning 'gcd' value =3 (recursive case:      m=)843,  n=99
The GCD of  843 and99 is 3

Answer 1

Это происходит потому, что состояние вызовов методов хранится в стеке (называемом «стеком вызовов»).

Как вы, возможно, знаете, стек является структурой данных First In Last Out.Это означает, что если вы положите предметов A, B, C и D в стек по порядку, первым элементом, который вы извлечете из стека, будет D, а последним элементом, который вы выберете, будет A.

Каждый раз, когда вы вызываете метод B из метода A, B помещается в стек вызовов и садится на вершину A. B сделает свое дело, а когда он вернется, он вытолкнут из стека, и A продолжитс тем, что он делал.

Следовательно, первый вызов gcd будет сделан последним, а последний вызов - первым, а все между ними будет перевернуто.

Это поведениеможет быть «смоделирован» с помощью java.util.Stack:

Stack<String> stack = new Stack<>();
for(int i = 0 ; i < 5 ; i++) {
    // simulating calling gcd recursively
    String s = "Call #" + i + " of gcd";
    stack.push(s);
    System.out.println(s);
}

for (int i = 0 ; i < 5 ; i++) {
    // simulating returning from all the calls to gcd
    System.out.print("Returning from ");
    System.out.println(stack.pop());
}

И он печатает:

Call #0 of gcd
Call #1 of gcd
Call #2 of gcd
Call #3 of gcd
Call #4 of gcd
Returning from Call #4 of gcd
Returning from Call #3 of gcd
Returning from Call #2 of gcd
Returning from Call #1 of gcd
Returning from Call #0 of gcd

Answer 2

Рекурсивный вызов появляется за одну строку до вывода на печать.Следовательно, первый выход будет базовым случаем, а последний выход будет первым уровнем рекурсивной функции.И именно поэтому вы получаете выходные данные в обратном порядке.