Editing Overlapping subproblems (section)

==Fibonacci sequence example==
In the following two implementations for calculating [[fibonacci sequence]], <code>fibonacci</code> uses regular recursion and <code>fibonacci_mem</code> uses [[memoization]]. <code>fibonacci_mem</code> is much more efficient as the value for any particular <code>n</code> is computed only once. 
{| style="width: auto;"
| <syntaxhighlight lang="python">
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, {}))  # 5
print(fibonacci(5))  # 5
</syntaxhighlight>
|}

When executed, the <code>fibonacci</code> function computes the value of some of the numbers in the sequence many times over, whereas <code>fibonacci_mem</code> reuses the value of <code>n</code> which was computed previously:
{|
|- 
! style="vertical-align:top;" | Recursive Version
! style="vertical-align:top;" | Memoization
|-
| style="vertical-align:top;" |
 f(5) = f(4) + f(3) = 5
        {{pipe}}      {{pipe}}
        {{pipe}}      f(3) = f(2) + f(1) = 2
        {{pipe}}             {{pipe}}      {{pipe}}
        {{pipe}}             {{pipe}}      f(1) = 1
        {{pipe}}             {{pipe}}
        {{pipe}}             f(2) = 1
        {{pipe}}
        f(4) = f(3) + f(2) = 3
               {{pipe}}      {{pipe}}
               {{pipe}}      f(2) = 1
               {{pipe}}
               f(3) = f(2) + f(1) = 2
                      {{pipe}}      {{pipe}}
                      {{pipe}}      f(1) = 1
                      {{pipe}}
                      f(2) = 1
| style="vertical-align:top;" |
 f(5) = f(4) + f(3) = 5
        {{pipe}}      {{pipe}}
        f(4) = f(3) + f(2) = 3
               {{pipe}}      {{pipe}}
               f(3) = f(2) + f(1) = 2
                      {{pipe}}      {{pipe}}
                      {{pipe}}      f(1) = 1
                      {{pipe}}
                      f(2) = 1
|}

The difference in performance may appear minimal with an <code>n</code> value of 5; however, as <code>n</code> increases, the [[computational complexity]] of the original <code>fibonacci</code> function grows exponentially. In contrast, the <code>fibonacci_mem</code> version exhibits a more linear increase in complexity.