The efficiency of recursion in MATLAB

46 views (last 30 days)
matar maoz
matar maoz on 27 Feb 2011
Edited: Jan on 28 Oct 2017
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 Comments
Jan
Jan on 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.

Sign in to comment.

Accepted Answer

John D'Errico
John D'Errico on 27 Feb 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.

More Answers (1)

Jan
Jan on 27 Feb 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 Comments
Walter Roberson
Walter Roberson on 28 Feb 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.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by