我正在尝试编写一个递归方法,用于查找通过n从m网格的左上角到右下角的所有可能方式的数量(不向上移动(。
变量key应该保存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;
}
}
这种行为上的差异是由类字段位于堆上而局部变量位于堆栈上这一事实引起的吗?我认为在递归方法中使用类字段比每次方法调用自己时创建一个局部字段更实用。
请帮助我更深入地理解这个问题。
如果类中有成员变量,则引用只存在一次。当使用递归函数时,所有递归调用都在相同的内存库上工作,所以在类对象中的相同内容上也是如此。
如果变量在函数中是本地的,那么在每个函数调用中,它都是一个新的存储和新的变量内容。
当使用上层代码时,递归调用本身也会更改键值,然后在";添加";命令键内容与递归调用之前不同。