The efficiency of recursion in MATLAB
17 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
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 commentaires
Joao Henriques
le 27 Oct 2017
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
le 28 Oct 2017
Modifié(e) : Jan
le 28 Oct 2017
@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.
Réponse acceptée
John D'Errico
le 27 Fév 2011
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 commentaires
Plus de réponses (1)
Jan
le 27 Fév 2011
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 commentaires
Walter Roberson
le 28 Fév 2011
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.
Voir également
Catégories
En savoir plus sur Loops and Conditional Statements dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!