Overlapping subproblems

<h2 id="fibonacci-sequence-example">Fibonacci sequence example</h2>
<p>In the following two implementations for calculating <a href="/facts/Fibonacci_sequence/mqxpAUQD">fibonacci sequence</a>, fibonacci uses regular recursion and fibonacci_mem uses <a href="/facts/Memoization/u08VhUKm">memoization</a>. fibonacci_mem is much more efficient as the value for any particular n is computed only once. 
</p>
<table><tbody><tr><td>def fibonacci(n):    if n <= 1:        return n    return fibonacci(n - 1) + fibonacci(n - 2)def fibonacci_mem(n, cache):    if n <= 1:        return n    if n in cache:        return cache[n]    cache[n] = fibonacci_mem(n - 1, cache) + fibonacci_mem(n - 2, cache)    return cache[n]print(fibonacci_mem(5, {}))  # 5print(fibonacci(5))  # 5</td></tr></tbody></table>
<p>When executed, the fibonacci function computes the value of some of the numbers in the sequence many times over, whereas fibonacci_mem reuses the value of n which was computed previously:
</p>
<table><tbody><tr><th>Recursive Version</th><th>Memoization</th></tr><tr><td>f(5) = f(4) + f(3) = 5       |      |       |      f(3) = f(2) + f(1) = 2       |             |      |       |             |      f(1) = 1       |             |       |             f(2) = 1       |       f(4) = f(3) + f(2) = 3              |      |              |      f(2) = 1              |              f(3) = f(2) + f(1) = 2                     |      |                     |      f(1) = 1                     |                     f(2) = 1</td><td>f(5) = f(4) + f(3) = 5       |      |       f(4) = f(3) + f(2) = 3              |      |              f(3) = f(2) + f(1) = 2                     |      |                     |      f(1) = 1                     |                     f(2) = 1</td></tr></tbody></table>
<p>The difference in performance may appear minimal with an n value of 5; however, as n increases, the <a href="/facts/Computational_complexity/Qenh22Ja">computational complexity</a> of the original fibonacci function grows exponentially. In contrast, the fibonacci_mem version exhibits a more linear increase in complexity.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Dynamic_programming/CLcabtmk">Dynamic programming</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Introduction to Algorithms, 2nd ed., (Cormen, Leiserson, Rivest, and Stein) 2001, p. 327. ISBN 0-262-03293-7. <a href="https://books.google.com/books?id=NLngYyWFl_YC&dq=introduction+to+algorithms&pg=PP1" target="_blank">https://books.google.com/books?id=NLngYyWFl_YC&dq=introduction+to+algorithms&pg=PP1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Introduction to Algorithms, 3rd ed., (Cormen, Leiserson, Rivest, and Stein) 2014, p. 384. ISBN 9780262033848. <a href="https://books.google.com/books?id=jUF9BAAAQBAJ&q=introduction+to+algorithms+3rd+edition" target="_blank">https://books.google.com/books?id=jUF9BAAAQBAJ&q=introduction+to+algorithms+3rd+edition</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Dynamic Programming: Overlapping Subproblems, Optimal Substructure, MIT Video. <a href="https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-13/" target="_blank">https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-13/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Overlapping subproblems open-in-new

Overlapping subproblems