recursive function hangs after a few steps

Question

ahmad habibi 2017-10-21

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/362539-recursive-function-hangs-after-a-few-steps

编辑： Roger Stafford 2017-10-21

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Roger Stafford 2017-10-21

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/362539-recursive-function-hangs-after-a-few-steps#answer_287054

编辑：Roger Stafford 2017-10-21

在 MATLAB Online 中打开

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Rik 2017-10-21

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/362539-recursive-function-hangs-after-a-few-steps#answer_287042

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.