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

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

0 голосов
/ 10 ноября 2018

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

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

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.

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

Ответы [ 3 ]

0 голосов
/ 10 ноября 2018

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

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

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) и как вы определяют его влияние на возвращаемое значение.

0 голосов
/ 10 ноября 2018

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

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 .. Никакой разницы нет.

0 голосов
/ 10 ноября 2018

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

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

...