Локальная переменная в рекурсии, сохраняющая значения?

Question

В настоящее время работаю над практикой / реализацией рекурсии и заметил кое-что, что противоречит всему, что я знаю, чтобы быть правдой в программировании

Рекурсивный метод

protected int getArea() {

    if(width <= 0)
        return 0;
    else if(width == 1)
        return 1;
    else {

        Triangle t2 = new Triangle(width - 1);
        int area = t2.getArea();//Area variable somehow is holding the values of previous calls, despite being instantiated in each new call?

        return area + width;

    }

}

Каким-то образом, локальная переменная, area, агрегирует значения из предыдущих вызовов в рекурсивном методе. Как это возможно, когда с каждым вызовом он создается? В каждом вызове появляется метод getArea() вызывается снова, предотвращая area переменная от удержания чего-либо в связи с тем, что getArea() вызов происходит до того, как методы return заявление.

Как это происходит?

Answer 1

Детали каждого вызова метода хранятся в стеке, после того как значение возвращается из вызова метода, выполнение возвращается к предыдущему методу, вызывающему текущий метод, значения локальной переменной и т. Д. будет храниться в стеке, и именно так эти значения используются при выполнении, когда это требуется программой. Проведите некоторые эксперименты с рекурсивными программами, чтобы больше узнать об этом.

Мое предложение было бы попробовать отладить рекурсивные программы с использованием точек останова на IDE, таких как eclipse или Intellij, это избавило бы от путаницы и внесло ясность в то, как работает рекурсия.

Answer 2

Я думаю, что вы смотрите на это неправильно. Если вы вызываете два метода. например.

public int test() {
    int x = getSomeInt(1);
    int y = getSomeInt(2);
    return x + y;
}

Вы когда-нибудь задавались вопросом, return x + y сделано или если значение x определяется до y? Это делается сверху вниз и настройка оператора y не начинается раньше getSomeInt(1) вернулся и его значение установлено как x, Итак, к вашему примеру:

protected int getArea() {
    if (width <= 0) {
        return 0;
    } elseif (width == 1) {
        return 1;
    } else {
        Triangle t2 = new Triangle(width - 1);
        int area = t2.getArea();
        return area + width;
    }
}

Так что если у вас есть треугольник с шириной 1 и позвонить getArea ты получаешь 1 назад.

Что произойдет, если вы сделаете это на треугольнике с шириной 2? Ну это создает t2 с шириной 1 и позвонить getArea в теме. Мы уже знаем результат, так как рассчитали его уже. area становится 1 а потом возвращается 1 + 2,

Что произойдет, если вы сделаете это с шириной 3? Это создаст t2 с шириной 2 и позвонить getArea() на что. Мы знаем, что возвращается 3 Исходя из вышесказанного, и в результате 3 + 3,

Рекурсивный метод вызывается с высоким with, но это тот, с 1 сначала определяется, затем 2, 3, 4, ... и, наконец, вызов, который вы на самом деле позвонили, имеет area что это добавляет его with к.

Каждый вызов метода не имеет ничего общего с вызываемым абонентом. Это тот же код, да, но это другой объект, и локальные переменные уникальны для вызова так же, как два вызова getSomeInt также есть две разные версии того, что называется первым параметром. Они не запутаны, если вы не мутируете или не передаете по ссылке.

Вызов метода для объекта очень похож на объект, являющийся аргументом в вызове. У рекурсивного вызова есть объект с меньшим width и в один прекрасный момент это ударит по базовому случаю. Вы могли бы сказать, что это то же самое:

public static int getArea(Triangle t) {
    if (t.width <= 0) {
        return 0;
    } elseif (t.width == 1) {
        return 1;
    } else {
        Triangle t2 = new Triangle(t.width - 1);
        int area = getArea(t2);
        return area + t.width;
    }
}

Опять же... метод рекурсивности ничего не меняет. Это не специальное лечение. Ему нужно завершить свои вызовы, прежде чем он сможет вернуть значение, как если бы вы использовали другой метод для получения области в getArea.. Нет разницы вообще.

Answer 3

Когда дело доходит до рекурсии, мне часто бывает полезно помнить, что то, что вы даете, это то, что вы получаете, то есть то, что вы получаете, когда вызываете свой рекурсивный метод, - это то, что вы решаете вернуть из него.

В этом случае, что вы получаете, когда пишете

int area = t2.getArea();

либо 0, 1 или же area + width,

Последний случай - это рекурсивный случай, когда вы рекурсивно определяете новый экземпляр Triangle с новой шириной, уменьшенной на 1, а затем вызываете .getArea() на что. Это функционально эквивалентно простому определению .getArea() как

protected int getArea(int width) {

    if(width <= 0)
        return 0;
    else if(width == 1)
        return 1;
    else {
        int area = getArea(width - 1);
        return area + width;
    }

}

Не имеет значения, звоните ли вы .getArea() из одного или другого экземпляра Triangle, Все, что имеет значение, это то, что вы определяете width быть при вызове (в данном случае width - 1) и как вы определяете его влияние на возвращаемое значение.