Блог

Я пытаюсь написать рекурсивный метод для определения числа всех возможных способов перемещения от верхнего левого до нижнего правого угла сетки m на n (без движения вверх).

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

Следующий код завершится необработанным исключением:

Элемент с тем же ключом уже добавлен. Ключ: 1,1

Это очень похоже, скажем, когда ваши начальные m и n равны 3 и 2 соответственно, функция (1, 2) попытается добавить свое значение в словарь с помощью ключа «1,1».:

 class Finder
{
    public Finder()
    {
        memo = new(new List<KeyValuePair<string, ulong>>
        { new KeyValuePair<string, ulong>("1,1", 1) });
    }

    private Dictionary<string, ulong> memo;
    private string key;
    private ulong value;

    public ulong FindPaths(int m, int n)
    {
        key = String.Format("{0},{1}", (m < n ? m : n), (m > n ? m : n));

        if (memo.ContainsKey(key))
        {
            return memo[key];
        }

        if (m == 0 || n == 0)
        {
            return 0;
        }

        value = FindPaths(m - 1, n)   FindPaths(m, n - 1);
        memo.Add(key, value);
        return value;
    }
}
 

И когда я изменяю предварительно вычисленный ключ в Add методе на то же выражение, которое вычисляет его в первую очередь, проблема исчезает:

 memo.Add(String.Format("{0},{1}", (m < n ? m : n), (m > n ? m : n)), value);
 

И теперь, если мы заменим поле класса локальной переменной, все будет работать так, как должно:

 class Finder
{
    public Finder()
    {
        memo = new(new List<KeyValuePair<string, ulong>>
        { new KeyValuePair<string, ulong>("1,1", 1) });
    }

    private Dictionary<string, ulong> memo;
    private ulong value;

    public ulong FindPaths(int m, int n)
    {
        string key;
        key = String.Format("{0},{1}", (m < n ? m : n), (m > n ? m : n));
        
        if (memo.ContainsKey(key))
        {
            return memo[key];
        }

        if (m == 0 || n == 0)
        {
            return 0;
        }

        value = FindPaths(m - 1, n)   FindPaths(m, n - 1);
        memo.Add(key, value);

        return value;
    }
}
 

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

Пожалуйста, помогите мне прийти к более глубокому пониманию этой темы.

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

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

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