<p>For example,
Look at the code that calculates the n-th Fibonacci number:</p>

<pre><code>fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}
</code></pre>

<p>The problem with this code is that it will generate stack overflow error for any number greater than 15 (in most computers).</p>

<p>Assume that we are calculating fib(10). In this process, say fib(5) is calculated a lot of times. Is there some way to store this in memory for fast retrieval and thereby increase the speed of recursion?</p>

<p>I am looking for a generic technique that can be used in almost all problems.</p>

[{'answer_id': 23964, 'author': 'jfs', 'author_id': 718, 'author_profile': 'https://Stackoverflow.com/users/718', 'pm_score': 1, 'selected': False, 'text': '<p>Try using a map, n is the key and its corresponding Fibonacci number is the value.</p>\n<p>@Paul</p>\n<p>Thanks for the info. I didn\'t know that. From the <a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow noreferrer">Wikipedia link</a> you mentioned:</p>\n<blockquote>\n<p>This technique of saving values that\nhave already been calculated is called\nmemoization</p>\n</blockquote>\n<p>Yeah I already looked at the code (+1). :)</p>\n'}, {'answer_id': 23968, 'author': 'Ed.', 'author_id': 522, 'author_profile': 'https://Stackoverflow.com/users/522', 'pm_score': 1, 'selected': False, 'text': '<p>What language is this?  It doesnt overflow anything in c...\nAlso, you can try creating a lookup table on the heap, or use a map</p>\n'}, {'answer_id': 23973, 'author': 'roo', 'author_id': 716, 'author_profile': 'https://Stackoverflow.com/users/716', 'pm_score': 1, 'selected': False, 'text': '<p>caching is generally a good idea for this kind of thing. Since fibonacci numbers are constant, you can cache the result once you have calculated it. A quick c/pseudocode example</p>\n\n<pre><code>class fibstorage {\n\n\n    bool has-result(int n) { return fibresults.contains(n); }\n    int get-result(int n) { return fibresult.find(n).value; }\n    void add-result(int n, int v) { fibresults.add(n,v); }\n\n    map&lt;int, int&gt;   fibresults;\n\n}\n\n\nfib(int n ) {\n    if(n==0 || n==1)\n            return 1;\n\n    if (fibstorage.has-result(n)) {\n        return fibstorage.get-result(n-1);\n    }\n\n    return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +\n             (fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )\n           );\n}\n\n\ncalcfib(n) {\n    v = fib(n);\n    fibstorage.add-result(n,v);\n}\n</code></pre>\n\n<p>This would be quite slow, as every recursion results in 3 lookups, however this should illustrate the general idea</p>\n'}, {'answer_id': 23975, 'author': 'fulmicoton', 'author_id': 446497, 'author_profile': 'https://Stackoverflow.com/users/446497', 'pm_score': 5, 'selected': True, 'text': '<p>Yes your insight is correct.\nThis is called <a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow noreferrer">dynamic programming</a>. It is usually a common memory runtime trade-off.</p>\n\n<p>In the case of fibo, you don\'t even need to cache everything :</p>\n\n<p>[edit]\nThe author of the question seems to be looking for a general method to cache rather than a method to compute Fibonacci. Search wikipedia or look at the code of the other poster to get this answer. Those answers are linear in time and memory.</p>\n\n<p>**Here is a linear-time algorithm O(n), constant in memory **</p>\n\n<pre><code>in OCaml:\n\nlet rec fibo n = \n    let rec aux = fun\n        | 0 -&gt; (1,1)\n        | n -&gt; let (cur, prec) = aux (n-1) in (cur+prec, cur)\n    let (cur,prec) = aux n in prec;;\n\n\n\nin C++:\n\nint fibo(int n) {\n    if (n == 0 ) return 1;\n    if (n == 1 ) return 1;\n    int p = fibo(0);\n    int c = fibo(1);\n    int buff = 0;\n    for (int i=1; i &lt; n; ++i) {\n      buff = c;\n      c = p+c;\n      p = buff;\n    };\n    return c;\n};\n</code></pre>\n\n<p>This perform in linear time. But log is actually possible !!!\nRoo\'s program is linear too, but way slower, and use memory.</p>\n\n<p><strong>Here is the log algorithm O(log(n))</strong></p>\n\n<p>Now for the log-time algorithm (way way way faster), here is a method :\nIf you know u(n), u(n-1), computing u(n+1), u(n) can be done by applying a matrix:</p>\n\n<pre><code>| u(n+1) |  = | 1 1 | | u(n)   |\n| u(n)   |    | 1 0 | | u(n-1) |    \n</code></pre>\n\n<p>So that you have :</p>\n\n<pre><code>| u(n)    |  = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |\n| u(n-1)  |    | 1 0 |       | u(0) |   | 1 0 |       | 1 |\n</code></pre>\n\n<p>Computing the exponential of the matrix has a logarithmic complexity. \nJust implement recursively the idea :</p>\n\n<pre><code>M^(0)    = Id\nM^(2p+1) = (M^2p) * M\nM^(2p)   = (M^p) * (M^p)  // of course don\'t compute M^p twice here.\n</code></pre>\n\n<p>You can also just diagonalize it (not to difficult), you will find the gold number and its conjugate in its eigenvalue, and the result will give you an EXACT mathematical formula for u(n). It contains powers of those eigenvalues, so that the complexity will still be logarithmic.</p>\n\n<p><em>Fibo is often taken as an example to illustrate Dynamic Programming, but as you see, it is not really pertinent.</em></p>\n\n<p>@John:\nI don\'t think it has anything to do with do with hash.</p>\n\n<p>@John2:\nA map is a bit general don\'t you think? For Fibonacci case, all the keys are contiguous so that a vector is appropriate, once again there are much faster ways to compute fibo sequence, see my code sample over there.</p>\n'}, {'answer_id': 23984, 'author': 'Fernando Barrocal', 'author_id': 2274, 'author_profile': 'https://Stackoverflow.com/users/2274', 'pm_score': 3, 'selected': False, 'text': '<p>This is called memoization and there is a very good article about memoization <a href="http://codebetter.com/blogs/matthew.podwysocki/default.aspx" rel="nofollow noreferrer">Matthew Podwysocki</a> posted these days. It uses Fibonacci to exemplify it. And shows the code in C# also. Read it <a href="http://codebetter.com/blogs/matthew.podwysocki/archive/2008/08/01/recursing-into-recursion-memoization.aspx" rel="nofollow noreferrer">here</a>.</p>\n'}, {'answer_id': 23985, 'author': 'olliej', 'author_id': 784, 'author_profile': 'https://Stackoverflow.com/users/784', 'pm_score': 1, 'selected': False, 'text': "<p>Is this a deliberately chosen example? (eg. an extreme case you're wanting to test)</p>\n\n<p>As it's currently O(1.6^n) i just want to make sure you're just looking for answers on handling the general case of this problem (caching values, etc) and not just accidentally writing poor code :D</p>\n\n<p>Looking at this specific case you could have something along the lines of:</p>\n\n<pre><code>var cache = [];\nfunction fib(n) {\n    if (n &lt; 2) return 1;\n    if (cache.length &gt; n) return cache[n];\n    var result = fib(n - 2) + fib(n - 1);\n    cache[n] = result;\n    return result;\n}\n</code></pre>\n\n<p>Which degenerates to O(n) in the worst case :D</p>\n\n<p>[Edit: * does not equal + :D ]</p>\n\n<p>[Yet another edit: the Haskell version (because i'm a masochist or something)</p>\n\n<pre><code>fibs = 1:1:(zipWith (+) fibs (tail fibs))\nfib n = fibs !! n\n</code></pre>\n\n<p>]</p>\n"}, {'answer_id': 23986, 'author': 'Kyle Cronin', 'author_id': 658, 'author_profile': 'https://Stackoverflow.com/users/658', 'pm_score': 0, 'selected': False, 'text': "<p>If you're using a language with first-class functions like Scheme, you can add memoization without changing the initial algorithm:</p>\n\n<pre><code>(define (memoize fn)\n  (letrec ((get (lambda (query) '(#f)))\n           (set (lambda (query value)\n                  (let ((old-get get))\n                    (set! get (lambda (q)\n                                (if (equal? q query)\n                                    (cons #t value)\n                                    (old-get q))))))))\n    (lambda args\n      (let ((val (get args)))\n        (if (car val)\n            (cdr val)\n            (let ((ret (apply fn args)))\n              (set args ret)\n              ret))))))\n\n\n(define fib (memoize (lambda (x)\n                       (if (&lt; x 2) x\n                           (+ (fib (- x 1)) (fib (- x 2)))))))\n</code></pre>\n\n<p>The first block provides a memoization facility and the second block is the fibonacci sequence using that facility. This now has an O(n) runtime (as opposed to O(2^n) for the algorithm without memoization).</p>\n\n<p><em>Note: the memoization facility provided uses a chain of closures to look for previous invocations. At worst case this can be O(n). In this case, however, the desired values are always at the top of the chain, ensuring O(1) lookup.</em></p>\n"}, {'answer_id': 24035, 'author': 'Darren Kopp', 'author_id': 77, 'author_profile': 'https://Stackoverflow.com/users/77', 'pm_score': 0, 'selected': False, 'text': "<blockquote>\n  <p>The problem with this code is that it will generate stack overflow error for any number greater than 15 (in most computers).</p>\n</blockquote>\n\n<p>Really? What computer are you using? It's taking a long time at 44, but the stack is not overflowing. In fact, your going to get a value bigger than an integer can hold (~4 billion unsigned, ~2 billion signed) before the stack is going to over flow (Fibbonaci(46)).</p>\n\n<p>This would work for what you want to do though (runs wiked fast)</p>\n\n<pre><code>class Program\n{\n    public static readonly Dictionary&lt;int,int&gt; Items = new Dictionary&lt;int,int&gt;();\n    static void Main(string[] args)\n    {\n        Console.WriteLine(Fibbonacci(46).ToString());\n        Console.ReadLine();\n    }\n\n    public static int Fibbonacci(int number)\n    {\n        if (number == 1 || number == 0)\n        {\n            return 1;\n        }\n\n        var minus2 = number - 2;\n        var minus1 = number - 1;\n\n        if (!Items.ContainsKey(minus2))\n        {\n            Items.Add(minus2, Fibbonacci(minus2));\n        }\n\n        if (!Items.ContainsKey(minus1))\n        {\n            Items.Add(minus1, Fibbonacci(minus1));\n        }\n\n        return (Items[minus2] + Items[minus1]);\n    }\n}\n</code></pre>\n"}, {'answer_id': 24098, 'author': 'Jakub Šturc', 'author_id': 2361, 'author_profile': 'https://Stackoverflow.com/users/2361', 'pm_score': 2, 'selected': False, 'text': '<p>According to <a href="http://en.wikipedia.org/wiki/Fibonacci_number" rel="nofollow noreferrer">wikipedia</a> Fib(0) should be 0 but it does not matter.</p>\n\n<p>Here is simple C# solution with for cycle:</p>\n\n<pre><code>ulong Fib(int n)\n{\n  ulong fib = 1;  // value of fib(i)\n  ulong fib1 = 1; // value of fib(i-1)\n  ulong fib2 = 0; // value of fib(i-2)\n\n  for (int i = 0; i &lt; n; i++)\n  {\n    fib = fib1 + fib2;\n    fib2 = fib1;\n    fib1 = fib;\n  }\n\n  return fib;\n}\n</code></pre>\n\n<p>It is pretty common trick to convert recursion to <a href="http://c2.com/cgi/wiki?TailRecursion" rel="nofollow noreferrer">tail recursion</a> and then to loop. For more detail see for example this <a href="http://www.isle.uiuc.edu/~akantor/teaching/discussionSessions/Accumulator%20Recursion.ppt" rel="nofollow noreferrer">lecture</a> (ppt).</p>\n'}, {'answer_id': 24169, 'author': 'ESRogs', 'author_id': 88, 'author_profile': 'https://Stackoverflow.com/users/88', 'pm_score': 2, 'selected': False, 'text': "<h1>Quick and dirty memoization in C++:</h1>\n\n<p>Any recursive method <code>type1 foo(type2 bar) { ... }</code> is easily memoized with <code>map&lt;type2, type1&gt; M</code>.</p>\n\n<pre><code>// your original method\nint fib(int n)\n{\n    if(n==0 || n==1)\n        return 1;\n    return fib(n-1) + fib(n-2);\n}\n\n// with memoization\nmap&lt;int, int&gt; M = map&lt;int, int&gt;();\nint fib(int n)\n{\n    if(n==0 || n==1)\n        return 1;\n\n    // only compute the value for fib(n) if we haven't before\n    if(M.count(n) == 0)\n        M[n] = fib(n-1) + fib(n-2);\n\n    return M[n];\n}\n</code></pre>\n\n<p>EDIT: @Konrad Rudolph<br>\nKonrad points out that std::map is not the fastest data structure we could use here.  That's true, a <code>vector&lt;something&gt;</code> should be faster than a <code>map&lt;int, something&gt;</code> (though it might require more memory if the inputs to the recursive calls of the function were not consecutive integers like they are in this case), but maps are convenient to use generally.  </p>\n"}, {'answer_id': 24175, 'author': 'Konrad Rudolph', 'author_id': 1968, 'author_profile': 'https://Stackoverflow.com/users/1968', 'pm_score': 1, 'selected': False, 'text': '<p>@ESRogs:</p>\n\n<p><code>std::map</code> lookup is <em>O</em>(log <em>n</em>) which makes it slow here. Better use a vector.</p>\n\n<pre><code>vector&lt;unsigned int&gt; fib_cache;\nfib_cache.push_back(1);\nfib_cache.push_back(1);\n\nunsigned int fib(unsigned int n) {\n    if (fib_cache.size() &lt;= n)\n        fib_cache.push_back(fib(n - 1) + fib(n - 2));\n\n    return fib_cache[n];\n}\n</code></pre>\n'}, {'answer_id': 24202, 'author': 'Lasse V. Karlsen', 'author_id': 267, 'author_profile': 'https://Stackoverflow.com/users/267', 'pm_score': 3, 'selected': False, 'text': '<p>If you\'re using C#, and can use <a href="http://www.postsharp.org/" rel="noreferrer">PostSharp</a>, here\'s a simple memoization aspect for your code:</p>\n\n<pre><code>[Serializable]\npublic class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer&lt;Object[]&gt;\n{\n    private Dictionary&lt;Object[], Object&gt; _Cache;\n\n    public MemoizeAttribute()\n    {\n        _Cache = new Dictionary&lt;object[], object&gt;(this);\n    }\n\n    public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)\n    {\n        Object[] arguments = eventArgs.GetReadOnlyArgumentArray();\n        if (_Cache.ContainsKey(arguments))\n        {\n            eventArgs.ReturnValue = _Cache[arguments];\n            eventArgs.FlowBehavior = FlowBehavior.Return;\n        }\n    }\n\n    public override void OnExit(MethodExecutionEventArgs eventArgs)\n    {\n        if (eventArgs.Exception != null)\n            return;\n\n        _Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;\n    }\n\n    #region IEqualityComparer&lt;object[]&gt; Members\n\n    public bool Equals(object[] x, object[] y)\n    {\n        if (Object.ReferenceEquals(x, y))\n            return true;\n\n        if (x == null || y == null)\n            return false;\n\n        if (x.Length != y.Length)\n            return false;\n\n        for (Int32 index = 0, len = x.Length; index &lt; len; index++)\n            if (Comparer.Default.Compare(x[index], y[index]) != 0)\n                return false;\n\n        return true;\n    }\n\n    public int GetHashCode(object[] obj)\n    {\n        Int32 hash = 23;\n\n        foreach (Object o in obj)\n        {\n            hash *= 37;\n            if (o != null)\n                hash += o.GetHashCode();\n        }\n\n        return hash;\n    }\n\n    #endregion\n}\n</code></pre>\n\n<p>Here\'s a sample Fibonacci implementation using it:</p>\n\n<pre><code>[Memoize]\nprivate Int32 Fibonacci(Int32 n)\n{\n    if (n &lt;= 1)\n        return 1;\n    else\n        return Fibonacci(n - 2) + Fibonacci(n - 1);\n}\n</code></pre>\n'}, {'answer_id': 24808, 'author': 'mgsloan', 'author_id': 1164871, 'author_profile': 'https://Stackoverflow.com/users/1164871', 'pm_score': 1, 'selected': False, 'text': '<p>Others have answered your question well and accurately - you\'re looking for memoization.</p>\n\n<p>Programming languages with <a href="http://en.wikipedia.org/wiki/Tail_recursion" rel="nofollow noreferrer">tail call optimization</a> (mostly functional languages) can do certain cases of recursion without stack overflow.  It doesn\'t directly apply to your definition of Fibonacci, though there are tricks..</p>\n\n<p>The phrasing of your question made me think of an interesting idea.. Avoiding stack overflow of a pure recursive function by only storing a subset of the stack frames, and rebuilding when necessary..  Only really useful in a few cases.  If your algorithm only conditionally relies on the context as opposed to the return, and/or you\'re optimizing for memory not speed.</p>\n'}, {'answer_id': 25417, 'author': 'Pat', 'author_id': 238, 'author_profile': 'https://Stackoverflow.com/users/238', 'pm_score': 0, 'selected': False, 'text': '<p>As other posters have indicated, <a href="http://en.wikipedia.org/wiki/Memoization" rel="nofollow noreferrer">memoization</a> is a standard way to trade memory for speed, here is some pseudo code to implement memoization for any function (provided the function has no side effects):</p>\n\n<p>Initial function code:</p>\n\n<pre><code> function (parameters)\n      body (with recursive calls to calculate result)\n      return result\n</code></pre>\n\n<p>This should be transformed to</p>\n\n<pre><code> function (parameters)\n      key = serialized parameters to string\n      if (cache[key] does not exist)  {\n           body (with recursive calls to calculate result)\n           cache[key] = result\n      }\n      return cache[key]\n</code></pre>\n'}, {'answer_id': 25419, 'author': 'Pat', 'author_id': 238, 'author_profile': 'https://Stackoverflow.com/users/238', 'pm_score': 0, 'selected': False, 'text': '<p>By the way Perl has a <a href="http://search.cpan.org/perldoc?Memoize" rel="nofollow noreferrer">memoize</a> module that does this for any function in your code that you specify.</p>\n\n<pre><code># Compute Fibonacci numbers\nsub fib {\n      my $n = shift;\n      return $n if $n &lt; 2;\n      fib($n-1) + fib($n-2);\n}\n</code></pre>\n\n<p>In order to memoize this function all you do is start your program with </p>\n\n<pre><code>use Memoize;\nmemoize(\'fib\');\n# Rest of the fib function just like the original version.\n# Now fib is automagically much faster ;-)\n</code></pre>\n'}, {'answer_id': 169900, 'author': 'dreeves', 'author_id': 4234, 'author_profile': 'https://Stackoverflow.com/users/4234', 'pm_score': 1, 'selected': False, 'text': "<p>Mathematica has a particularly slick way to do memoization, relying on the fact that hashes and function calls use the same syntax:</p>\n\n<pre><code>fib[0] = 1;\nfib[1] = 1;\nfib[n_] := fib[n] = fib[n-1] + fib[n-2]\n</code></pre>\n\n<p>That's it.  It caches (memoizes) fib[0] and fib[1] off the bat and caches the rest as needed.  The rules for pattern-matching function calls are such that it always uses a more specific definition before a more general definition.</p>\n"}, {'answer_id': 300686, 'author': 'Daniel Crenna', 'author_id': 18440, 'author_profile': 'https://Stackoverflow.com/users/18440', 'pm_score': 1, 'selected': False, 'text': '<p>One more excellent resource for C# programmers for recursion, partials, currying, memoization, and their ilk, is Wes Dyer\'s blog, though he hasn\'t posted in awhile. He explains memoization well, with solid code examples here:\n<a href="http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx" rel="nofollow noreferrer">http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx</a> </p>\n'}, {'answer_id': 365050, 'author': 'thelsdj', 'author_id': 163, 'author_profile': 'https://Stackoverflow.com/users/163', 'pm_score': 0, 'selected': False, 'text': "<p>@lassevk:</p>\n\n<p>This is awesome, exactly what I had been thinking about in my head after reading about memoization in <em>Higher Order Perl</em>. Two things which I think would be useful additions:</p>\n\n<ol>\n<li>An optional parameter to specify a static or member method that is used for generating the key to the cache.</li>\n<li>An optional way to change the cache object so that you could use a disk or database backed cache.</li>\n</ol>\n\n<p>Not sure how to do this sort of thing with Attributes (or if they are even possible with this sort of implementation) but I plan to try and figure out.</p>\n\n<p>(Off topic: I was trying to post this as a comment, but I didn't realize that comments have such a short allowed length so this doesn't really fit as an 'answer')</p>\n"}]
['https://Stackoverflow.com/questions/23962', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/184/']