Fibonacci with Memoization

Compute fib(n) recursively and cache each fib(k) in a memo array so each subproblem is solved at most once. Turns exponential recursion into a linear walk, the canonical introduction to dynamic programming.

Algorithm

Canonical input n = 6 produces fib(6) = 8. The replay shows the descent for fib(6) -> fib(5) -> ... -> fib(0) then four cache hits on the unwind (one per repeat-call subproblem).

Basic Implementation

basic.f90

module fib_mod
    implicit none
    integer :: memo(0:6) = -1
contains
    recursive function fib(n) result(v)
        integer, intent(in) :: n
        integer :: v
        if (memo(n) /= -1) then
            v = memo(n)
            return
        end if
        if (n < 2) then
            memo(n) = n
            v = n
            return
        end if
        v = fib(n - 1) + fib(n - 2)
        memo(n) = v
    end function fib
end module fib_mod

program dp_fibonacci_memo
    use fib_mod
    implicit none
    integer :: result, i
    result = fib(6)
    print '(I0)', result
    do i = 0, 6
        print '(A,I0,A,I0)', 'memo(', i, ') = ', memo(i)
    end do
end program dp_fibonacci_memo

Complexity

Time: O(n) with memoization (vs. O(2^n) without)
Space: O(n) memo plus O(n) call stack

Implementation notes

Fortran: a 0-indexed integer :: memo(0:6) = -1 is the smallest possible memo for fib(6). The sentinel -1 distinguishes "not computed yet" from a real fib(k) value, which is always >= 0. Pass the memo through the module rather than as an argument to keep the recursive signature compact.
The replay shows each fib(k) call and the memo state after, marking the cache-hit steps distinctly so the viewer can count how many descents were avoided.

memoization Reuse cached subproblem results instead of re-descending.