The efficiency of recursion in MATLAB

Question

matar maoz 2011-2-27

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2126-the-efficiency-of-recursion-in-matlab

编辑： Jan 2017-10-28

I wanted to implement an algorithm I wrote with a recursion loop. At first I got an ERROR saying that I ran ran out of memory, and after working on saving memory, I got a messege saying that the default maximum for MATLAB is a recourse of 500 steps.

Are there ways to improve using recursion without chopping important data, or risking crashing your computer?

Matar Maoz

3 个评论
显示 1更早的评论隐藏 1更早的评论

Joao Henriques 2017-10-27

I have to say that this seems like the wrong kind of attitude.

Other languages are perfectly capable of handling recursive algorithms. These kinds of algorithms are taught in CS classes and for some tasks they really are the most elegant way to solve a problem, e.g. specialized graph or tree algorithms.

This is more a matter of how many resources does each Matlab function call take. I think we can all agree that there should be an effort to make such function calls as lightweight as possible (which I'm sure Mathworks is doing). Workspaces don't have to be "heavyweight". If they were lighter, recursions well into the thousands would be fine (just like in C++, Python, etc).

Jan 2017-10-28

编辑：Jan 2017-10-28

在 MATLAB Online 中打开

@Joao Henriques: Attitude? The given advice is based on knowledge about Matlab and experiences with efficient programming techniques, not an opinion or attitude. Even a "light-weight" overhead for a function call gets heavy in total, if it is needed thousands or millions of times. You can exhaust the stack (or heap) space in C, C++ and Python as well as in Matlab. A direct comparison between Matlab and C++ is not the point, because these languages have different natures. You cannot simply reduce the heaviness of a local workspace without changing the language itself. Surely there is no unnecessary junk in the overhead for calling functions and creating local workspaces in Matlab.

Of course some algorithms taught in computer science classes are elegant, but not useful in productive code. A famous example is the Fibonacci sequence: It is useful to teach students how to write a recursive method to determine the n.th Fibonacci number F(n), but Binet's formula is much leaner:

F(n) = round(phi^n / sqrt(5)), with phi := (1 + sqrt(5)) / 2

There is no need for an attitude in this question, because the efficiency of the implementation with recursion or iteration can be measured. Elegance of an implementation is nice and matters for debugging, so I implement recursions usually to cross check the results of the faster iterative methods. And if several 1000 recursive calls are needed for such a test, the RecursionLimit can be set accordingly.

请先登录，再进行评论。

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

Answer 1

John D'Errico 2011-2-27

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2126-the-efficiency-of-recursion-in-matlab#answer_3335

在 MATLAB Online 中打开

Many recursive algorithms are actual terrible wastes of time and memory. You end up computing and recomputing the same thing many times. Instead, look for memoization schemes, that avoid the recomputations by saving those values. For example, look at the Fibonacci sequence.

F(n+1) = F(n) + F(n-1)

Suppose we compute F(5), by calling recursively for the values of F(4) and F(3). Then F(4) is gotten as the sum of F(3) + F(2), but F(3) is the sum of F(2)+F(1), etc. In the end, we can see that many of these terms will have been accessed multiple times.

The point is, while recursion seems an elegant solution, it is in reality a terrible solution here if you simply do the direct recursive calls.

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

请先登录，再进行评论。

Answer 2

Jan 2011-2-27

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2126-the-efficiency-of-recursion-in-matlab#answer_3333

在 MATLAB Online 中打开

You can set the recursion limit manually:

set(0, 'RecursionLimit', 1000)

But as Matt pointed out, such a massive recursive method consumes a lot of memory. Because every recursive program can be implemented without recursion also, I suggest to avoid the recursion in general if it exceeds 20 levels.

3 个评论
显示 1更早的评论隐藏 1更早的评论

Jan 2011-2-28

Then simply avoid the recursion.

Walter Roberson 2011-2-28

Matar, are you indicating that you have had your computer crash due to recursion in Matlab? Not just Matlab crashing? If using recursion in Matlab can lead to your entire computer crashing, then I'm sure Mathworks would be very interested in seeing the code.

请先登录，再进行评论。