recursive function hangs after a few steps

im trying to set up a recursion script for population extinction of the form x_n+1 = a + b*(x_n) + c*(x_n)^2 this is what i have for a,b,c=.1,.6,.3 it works fine until around 25 steps, but it will not run anything higher.

any help?

function [ answer ] = extinction(n)
  if n > 0
    answer = (.1) + (.6) * extinction(n-1) + (.3) * (extinction(n-1))^2;
  else
    answer = 0;
  end
end

Answer 1

[Roger Stafford]

The trouble with your recursion is that for an original call with, say, n = 26 it will recursively call on itself twice with n = 25. For each of these it will call on itself twice again with n = 24, which gives a total of four calls. As you can see, following this reasoning, it will eventually result in 2^26 = 67,108,864 calls with n = 0. The total number of calls would be the sum of all these, which is 1+2+2^2+2^3+...+2^26 = 2^27-1 = 134,217,727, an enormous number of calls. In general for an original number n, it will have to make 2^(n+1)-1 calls altogether.

As the answers by Rik and Walter demonstrate, there exist much more efficient methods of computation than with this horrible “doubling”. Even if you made the simple change:

.....
if n > 0
  t = extinction(n-1);
  answer = .1 + .6*t + .3*t^2;
.....

you could avoid this difficulty.

Answer 2

[Rik]

I think you should run this in a loop, not as a recursive function. Just pre-allocate an array and loop through it. Added bonus is that it is faster (no need to set up a separate stack for a new function) and you will have access to intermediary answers.

Answer 3

[Walter Roberson]

https://www.mathworks.com/help/matlab/ref/memoize.html