Может кто-нибудь объяснить мне следующий Java фрагмент для рекурсии?

Question

public class GetElementWithoutPop {

    public static void main(String args[]) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);
        stack.push(60);
        System.out.println("value is: " + GetElementWithoutPop.getStackElement(stack, 3));
        System.out.println("stack is " + stack);

        // Using Java
        int position = 3;
        Integer result = stack.get(position);
        System.out.println(result);
    }

    public static <T> T getStackElement(Stack<T> stack, int index) {
        if (index == 0) {
            return stack.peek();
        }

        T x = stack.pop();
        try {

            return getStackElement(stack, index - 1);
        } finally {
            stack.push(x);
        }
    }

}

Пока индекс не станет 0 из 3, это все хорошо и просто, но после этого код возвращается к блоку try, а затем снова к блоку finally и индекс начинает увеличиваться сам по себе. путь назад к 3 и stack.push(x) возвращает стек в исходное состояние.

Как это происходит?
Довольно плохо знаком с рекурсиями, и мне нужно это понять!

Answer 1

Это происходит потому, что каждый вызов функции имеет свой собственный уникальный контекст для той же функции, поэтому переменная x хранит перенесенную переменную и вызывает рекурсивно, чтобы получить дополнительное значение, но это значение сохраняется в x следующего вызова функции, при этом возвращая finally блок запускается, и каждое уникальное значение x в каждом вызове функции снова выдвигается

T x = stack.pop();           // this value remains stored in the function call stack
    try {

        return getStackElement(stack, index - 1);  // same function runs for further case (n-1) th and stores the value in its own x variable in its context
    } finally {
        stack.push(x);      // after the control returns, this copy of function has its  unique x variable and that is pushed again
    }

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

Некоторые шаги

1) Экземпляр вызова функции с индексом 3 вызывает функцию с индексом 2

2) Экземпляр вызова функции с индексом 2 вызывает функцию с индексом 1

3) Экземпляр вызова функции с индексом 1 вызывает функцию с индексом 0

4) Элемент управления возвращает

5) Теперь элемент управления возвращается к экземпляру со значением индекса 1

6) Элемент управления возвращается даже из этого экземпляра и теперь возвращается к экземпляру с индексом 2

T Это как накручивание, а затем раскручивание, при решении проблем с рекурсией нам часто приходится решать, хотим ли мы выполнить какую-то работу по вызову для n, а затем вызывать для n-1 ИЛИ вызывать для n-1, позвольте элементу управления вернуться и затем сделать какую-то работу