是否有某种方法可以通过记住子节点来加快递归？
例如，
查看计算第n个斐波那契数的代码：
fib(int n)
{
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
此代码的问题在于，对于任何大于15的数字(在大多数计算机中)，它将生成堆栈溢出错误。
假设我们正在计算fib(10)。在这个过程中，fib(5)被多次计算。是否有某种方法可以将其存储在内存中以便快速检索，从而提高递归速度？
我正在寻找一种可以用于几乎所有问题的通用技术。
解决方案
回答
尝试使用地图，n是键，其对应的斐波那契数是值。
保罗
谢谢(你的)信息。我不知道我们在Wikipedia链接中提到：
This technique of saving values that have already been calculated is called memoization
是的，我已经看过代码(+1)。 :)
回答
这是什么语言？它不会在C中溢出任何东西...
另外，我们可以尝试在堆上创建查找表，或者使用映射
回答
对于这种事情，缓存通常是个好主意。由于斐波那契数是恒定的，因此我们可以在计算出结果后将其缓存。快速的c / pseudocode示例
class fibstorage {
bool has-result(int n) { return fibresults.contains(n); }
int get-result(int n) { return fibresult.find(n).value; }
void add-result(int n, int v) { fibresults.add(n,v); }
map<int, int> fibresults;
}
fib(int n ) {
if(n==0 || n==1)
return 1;
if (fibstorage.has-result(n)) {
return fibstorage.get-result(n-1);
}
return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +
(fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )
);
}
calcfib(n) {
v = fib(n);
fibstorage.add-result(n,v);
}
这会非常慢，因为每次递归都会导致3次查找，但这应该可以说明总体思路
回答
是的，见解是正确的。
这称为动态编程。通常，这是常见内存运行时的折衷方案。
对于fibo，我们甚至不需要缓存所有内容：
[编辑]
这个问题的作者似乎正在寻找一种通用的缓存方法，而不是一种计算斐波那契的方法。搜索维基百科或者查看其他海报的代码以获得此答案。这些答案在时间和记忆上都是线性的。
这里是线性时间算法O(n)，在内存中恒定
in OCaml:
let rec fibo n =
let rec aux = fun
| 0 -> (1,1)
| n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
let (cur,prec) = aux n in prec;;
in C++:
int fibo(int n) {
if (n == 0 ) return 1;
if (n == 1 ) return 1;
int p = fibo(0);
int c = fibo(1);
int buff = 0;
for (int i=1; i < n; ++i) {
buff = c;
c = p+c;
p = buff;
};
return c;
};
这以线性时间执行。但是日志实际上是可能的！
Roo的程序也是线性的，但是速度较慢，并且使用内存。
这是对数算法O(log(n))
现在，对于日志记录时间算法(更快的方式)，这是一个方法：
如果知道u(n)，u(n-1)，计算u(n + 1)，u(n)，可以通过应用矩阵来完成：
| u(n+1) | = | 1 1 | | u(n) | | u(n) | | 1 0 | | u(n-1) |
这样就可以了：
| u(n) | = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 | | u(n-1) | | 1 0 | | u(0) | | 1 0 | | 1 |
计算矩阵的指数具有对数复杂度。
只需递归地实现这个想法：
M^(0) = Id M^(2p+1) = (M^2p) * M M^(2p) = (M^p) * (M^p) // of course don't compute M^p twice here.
我们也可以将其对角线化(不难)，我们会在其特征值中找到黄金数及其共轭，结果将为我们提供u(n)的精确数学公式。它包含那些特征值的幂，因此复杂度仍然是对数的。
经常以Fibo为例来说明动态编程，但是正如我们所看到的，它并不是真正相关的。
@约翰：
我认为这与哈希无关。
@ John2：
地图有点一般吧？对于Fibonacci情况，所有键都是连续的，因此向量是合适的，再次有更快的方法来计算fibo序列，请参阅那边的代码示例。
回答
这就是所谓的回忆，这些天马修·波德维索克(Matthew Podwysocki)发表了一篇有关回忆的很好的文章。它以斐波那契为例。并在Calso中显示代码。在这里阅读。
回答
这是故意选择的示例吗？ (例如，我们要测试的极端情况)
因为它目前是O(1.6 ^ n)，所以我只想确保我们只是在寻找处理此问题的一般情况(缓存值等)的答案，而不仅仅是不小心编写不良代码：
查看此特定情况，我们可能会遇到以下问题：
var cache = [];
function fib(n) {
if (n < 2) return 1;
if (cache.length > n) return cache[n];
var result = fib(n - 2) + fib(n - 1);
cache[n] = result;
return result;
}
在最坏的情况下退化为O(n)：D
[编辑：*不等于+：D]
[另外编辑：Haskell版本(因为我是受虐狂之类的人)
fibs = 1:1:(zipWith (+) fibs (tail fibs)) fib n = fibs !! n
]
回答
如果我们正在使用具有一流功能(例如Scheme)的语言，则可以添加备注，而无需更改初始算法：
(define (memoize fn)
(letrec ((get (lambda (query) '(#f)))
(set (lambda (query value)
(let ((old-get get))
(set! get (lambda (q)
(if (equal? q query)
(cons #t value)
(old-get q))))))))
(lambda args
(let ((val (get args)))
(if (car val)
(cdr val)
(let ((ret (apply fn args)))
(set args ret)
ret))))))
(define fib (memoize (lambda (x)
(if (< x 2) x
(+ (fib (- x 1)) (fib (- x 2)))))))
第一块提供记忆功能，第二块是使用该功能的斐波那契数列。现在，它具有O(n)运行时(与没有记忆的算法的O(2 ^ n)相对)。
注意：提供的备忘录功能使用闭包链来查找先前的调用。在最坏的情况下，这可能是O(n)。但是，在这种情况下，所需值始终位于链的顶部，从而确保了O(1)查找。
回答
The problem with this code is that it will generate stack overflow error for any number greater than 15 (in most computers).
真的吗？我们正在使用什么计算机？在44点花费很长时间，但是堆栈没有溢出。实际上，在堆栈溢出之前，我们要获得的值可能大于整数(约40亿个无符号，约20亿个有符号)(Fibbonaci(46))。
这将适合我们想做的事情(运行速度很快)
class Program
{
public static readonly Dictionary<int,int> Items = new Dictionary<int,int>();
static void Main(string[] args)
{
Console.WriteLine(Fibbonacci(46).ToString());
Console.ReadLine();
}
public static int Fibbonacci(int number)
{
if (number == 1 || number == 0)
{
return 1;
}
var minus2 = number - 2;
var minus1 = number - 1;
if (!Items.ContainsKey(minus2))
{
Items.Add(minus2, Fibbonacci(minus2));
}
if (!Items.ContainsKey(minus1))
{
Items.Add(minus1, Fibbonacci(minus1));
}
return (Items[minus2] + Items[minus1]);
}
}
回答
根据维基百科，Fib(0)应该为0，但这并不重要。
这是带有for循环的简单Csolution：
ulong Fib(int n)
{
ulong fib = 1; // value of fib(i)
ulong fib1 = 1; // value of fib(i-1)
ulong fib2 = 0; // value of fib(i-2)
for (int i = 0; i < n; i++)
{
fib = fib1 + fib2;
fib2 = fib1;
fib1 = fib;
}
return fib;
}
将递归转换为尾递归然后进行循环是很常见的技巧。有关更多详细信息，请参见本讲课(ppt)。
回答
任何递归方法" type1 foo(type2 bar){...}"都可以通过map <type2，type1> M轻松地记住。
// your original method
int fib(int n)
{
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
// with memoization
map<int, int> M = map<int, int>();
int fib(int n)
{
if(n==0 || n==1)
return 1;
// only compute the value for fib(n) if we haven't before
if(M.count(n) == 0)
M[n] = fib(n-1) + fib(n-2);
return M[n];
}
编辑：@Konrad Rudolph
Konrad指出std :: map并不是我们可以在此处使用的最快的数据结构。没错，" vector <something>"应该比" map <int，something>"更快(尽管如果函数的递归调用的输入不是连续整数，则可能需要更多内存) )，但一般来说地图使用起来很方便。
回答
@ESRogs：
std :: map查找是O(log n)，这使它变慢。最好使用向量。
vector<unsigned int> fib_cache;
fib_cache.push_back(1);
fib_cache.push_back(1);
unsigned int fib(unsigned int n) {
if (fib_cache.size() <= n)
fib_cache.push_back(fib(n - 1) + fib(n - 2));
return fib_cache[n];
}
回答
如果我们使用的是C＃，并且可以使用PostSharp，则以下是代码的简单备注方面：
[Serializable]
public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]>
{
private Dictionary<Object[], Object> _Cache;
public MemoizeAttribute()
{
_Cache = new Dictionary<object[], object>(this);
}
public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)
{
Object[] arguments = eventArgs.GetReadOnlyArgumentArray();
if (_Cache.ContainsKey(arguments))
{
eventArgs.ReturnValue = _Cache[arguments];
eventArgs.FlowBehavior = FlowBehavior.Return;
}
}
public override void OnExit(MethodExecutionEventArgs eventArgs)
{
if (eventArgs.Exception != null)
return;
_Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;
}
#region IEqualityComparer<object[]> Members
public bool Equals(object[] x, object[] y)
{
if (Object.ReferenceEquals(x, y))
return true;
if (x == null || y == null)
return false;
if (x.Length != y.Length)
return false;
for (Int32 index = 0, len = x.Length; index < len; index++)
if (Comparer.Default.Compare(x[index], y[index]) != 0)
return false;
return true;
}
public int GetHashCode(object[] obj)
{
Int32 hash = 23;
foreach (Object o in obj)
{
hash *= 37;
if (o != null)
hash += o.GetHashCode();
}
return hash;
}
#endregion
}
这是一个使用它的示例斐波那契实现：
[Memoize]
private Int32 Fibonacci(Int32 n)
{
if (n <= 1)
return 1;
else
return Fibonacci(n - 2) + Fibonacci(n - 1);
}
回答
其他人已经很好地回答了问题，并且我们正在准确地寻找备忘录。
具有尾部调用优化功能的编程语言(主要是功能语言)可以执行某些递归情况而不会导致堆栈溢出。尽管有一些技巧，但它并不直接适用于我们对斐波那契的定义。
我们问题的措辞使我想到了一个有趣的主意。通过仅存储堆栈框架的子集并在必要时进行重建，避免了纯递归函数的堆栈溢出。仅在某些情况下非常有用。如果算法仅有条件地依赖于上下文而不是返回，并且/或者我们针对内存进行了优化，而不是提高速度。
回答
正如其他张贴者所指出的那样，记忆是一种以内存换取速度的标准方法，以下是一些用于实现任何功能记忆的伪代码(前提是该功能没有副作用)：
初始功能代码：
function (parameters)
body (with recursive calls to calculate result)
return result
这应该转换为
function (parameters)
key = serialized parameters to string
if (cache[key] does not exist) {
body (with recursive calls to calculate result)
cache[key] = result
}
return cache[key]
回答
顺便说一句，Perl拥有一个备注模块，可为我们指定的代码中的任何功能执行此操作。
# Compute Fibonacci numbers
sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}
为了记住该功能，我们要做的就是从以下位置启动程序
use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.
# Now fib is automagically much faster ;-)
回答
Mathematica有一种特别的方式来做记忆，它依赖于散列和函数调用使用相同语法的事实：
fib[0] = 1; fib[1] = 1; fib[n_] := fib[n] = fib[n-1] + fib[n-2]
而已。它从头开始缓存(记忆)fib [0]和fib [1]，并根据需要缓存其余部分。模式匹配函数调用的规则是这样的，它总是在使用更通用的定义之前始终使用更具体的定义。
回答
Wes Dyer的博客是Cprogrammers另一个更出色的资源，可用于递归，局部，计算，记忆和它们的同类，尽管他尚未发布。他很好地解释了记忆，这里有可靠的代码示例：
http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx
回答
@lassevk：
太棒了，这正是我在阅读了High Order Perl中的记忆后脑子里一直在想的东西。我认为有两点有用的补充：
- 一个可选参数，用于指定用于生成高速缓存密钥的静态或者成员方法。
- 更改缓存对象的一种可选方法，以便我们可以使用磁盘或者数据库支持的缓存。
不知道如何使用Attributes来做这种事情(或者，即使使用这种实现也可以做到)，但我计划尝试找出。
(非主题：我试图将其发布为评论，但是我没有意识到评论的允许长度太短，因此这实际上不适合作为"答案")
