memoization in matlab

Memoization is a technique used in dynamic programming that involves caching previously computed results of a function to avoid redundant computation. In Matlab, we can use nested functions and persistent variables to implement memoization.

Here's an example of how we can memoize a recursive function in Matlab:

main.m
function result = memoizedFibonacci(n)
persistent memoTable

if isempty(memoTable)
    memoTable = containers.Map('KeyType', 'double', 'ValueType', 'double'); % create a hash table to store computed results
end

if memoTable.isKey(n)
    result = memoTable(n); % if the result is already computed, retrieve it from the memo table
else
    if n <= 2
        result = 1;
    else
        result = memoizedFibonacci(n-1) + memoizedFibonacci(n-2);
    end
    memoTable(n) = result; % cache the computed result in the memo table
end

end
534 chars
20 lines

In this example, we use a hash table memoTable to store the Fibonacci numbers already computed. The isKey method checks if the result for input n is already computed, and if so, we retrieve it from the table, otherwise we compute the result using the memoized recursive function and store it in the table.

Note that we use a persistent variable to ensure that the memoTable object is not destroyed when the function exits, and is available for future calls to the memoized function.

gistlibby LogSnag