The efficiency of recursion in MATLAB

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

[Matt Tearle]

I hate to ask the obvious, but is there any reason you actually need more than 500 levels of recursion? Keeping 500 workspaces is a brutal piece of memory management, and the algorithm is surely going to take forever - is there no other way to approach the problem? (I assume you have tested this thoroughly on small cases, so you know you're not hitting an infinite recursion)

[Joao Henriques]

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]

@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]

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.

Answer 2

[Jan]

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.

[matar maoz]

I saw I could extend my recursion level limit.

the problem is avoiding crashing my computer.

[Jan]

Then simply avoid the recursion.

[Walter Roberson]

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.