MATLAB: The efficiency of recursion in MATLAB

memoizationmemoryrecursion

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

Best Answer

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.

Related Solutions

MATLAB: Calling the same function from within the function?

This is called "recursion", and it is legal in most programming languages.

Every linear procedure can be rewritten as a recursive procedure.

Every recursive procedure can be rewritten as a linear procedure, provided that sufficient dynamic memory allocation is permitted. Doing so might be awkward and might require a lot of extra memory, but it is always possible.

There is a subset of recursion called "tail recursion" that can be quite efficient to execute.

Recursive functions are very important in theoretical computer science. The theory of what can be deterministically computed talks about "Primitive Recursive Functions"

MATLAB: Helped needed in Fibonacci Sequence code

Hello Cici. We can solve this by introducing another variable count into the function as shown below.

function[F_n, count] = Fibonacci(n, count)
    count = 1;
    
    if n == 2
        F_n = 1; 
    elseif n == 1
        F_n = 0;
    else
        [F_n_1, count_1] = Fibonacci(n-1);
        [F_n_2, count_2] = Fibonacci(n-2);
        F_n = F_n_1 + F_n_2;
        count = count + count_1 + count_2;
    end
end

Now your function returns both the

Fibonacci number as well as the number of times the function was called.

You may capture only the count in variable ans using this code snippet for the desired value of n.

[~, ans] = Fibonacci(n);

Hope this helps. :)

Best Answer

Related Solutions

MATLAB: Calling the same function from within the function?

MATLAB: Helped needed in Fibonacci Sequence code

Related Question