CODEWITHSUNDEEP
matlab
Robert Israel
Robert Israel

Reputation: 173

How to memoize a recursive function in Matlab

I'm using Matlab R2018a. This has a "memoize" function, which works at top level, but I don't see how to use it for recursive functions. For example, I tried this:

function z = recfib(n)
  if n == 1
      z = 1;
  else
      z = memfib(n-1)+memfib(n-2);
  end
  fprintf('computed f(%d)=%d',n,z);
end

and then

memfib = memoize(@recfib);

But this doesn't work, as calls to memfib or recfib produce an error:

Undefined function or variable 'memfib'.

Upvotes: 1

Views: 286

Answers (1)

Andrew Janke
Andrew Janke

Reputation: 23888

You need to stick that memfib somewhere that the calls inside the function can see it. If you just do memfib = memoize(@recfib) at the command line or in calling code, you end up with a memfib variable in the base/caller workspace, not a globally-visible memfib function.

I think you can do this with a persistent variable inside the recfib function. This works for me in R2019b.

function z = recfib(n)
  persistent memfib
  if isempty(memfib)
    memfib = memoize(@recfib);
  end

  if n <= 1
      z = 1;
  else
      z = memfib(n-1)+memfib(n-2);
  end
  fprintf('computed f(%d)=%d\n',n,z);
end

Running it twice shows the memoization happening:

>> recfib(8)
computed f(1)=1
computed f(0)=1
computed f(2)=2
computed f(3)=3
computed f(4)=5
computed f(5)=8
computed f(6)=13
computed f(7)=21
computed f(8)=34
ans =
    34
>> recfib(8)
computed f(8)=34
ans =
    34
>>

(Also, you've got a bug in the base case test; it needs to be n <= 1, not n == 1, to catch the 0 and -1 cases, because that memfib(n-2) line ends up calling memfib(0) when n = 2.)

Upvotes: 4

Related Questions