Profiling of inefficient recursive Fibonacci series function

I am asked to profile an intentionally inefficient code. Following code will overtime with a huge input:

function f = fibo(n)
    if n <= 2
        f = 1;
    else
        f = fibo(n-2) + fibo(n-1);
    end
end

I used a persistente variable, to create an array that reflects the recursion calls:

function [f, trace]=fibo_trace(n,v)%with persistent variable 'trc'
persistent trc;
if isempty(trc)
    trc=v;
end
if n<=2
    trc=[trc n];
    f=1;
else
    trc=[trc n];
    f=fibo_trace(n-2)+fibo_trace(n-1);
end
trace=trc;
end

That works flawlessly when I run the function with followin code:

[f trace] = fibo_trace(6,[])

And this is what the code returns:

f = 8

trace = 6 4 2 3 1 2 5 3 1 2 4 2 3 1 2,

which is OK, since the trace vector shows how inefficient the original code is. Now my problem is, it is an assigment for a MOOC platform and the solution with the persistent variable won't work because the the automated grader will run the function a number of times with random inputs and it will not clear the function. Without the persistent variable I must split the recursive calls in two code lines and I am struggling now to compute the nth fibonacci number:

Can anyone give a clue? The creation of the array works but I honestly don't know how to deal with the two recursive call lines to compute the fibonacci.

Answer 1

[Stephen23]

Perhaps something like this:

[val,vec] = fibo(6)

val = 8

vec = 1×15

8 5 3 2 1 1 1 2 1 1 3 2 1 1 1

●

function [f,t] = fibo(n)
    if n <= 2
        f = 1;
        t = f;
    else
        [f2,t2] = fibo(n-2);
        [f1,t1] = fibo(n-1);
        f = f2+f1;
        t = [f,t1,t2];
    end
end

It might be including the 1's repeatedly, so that gives you something to debug :)

[Carlos Rueda]

Thank you Stephen for the quick answer. I actually solved it a few minutes after posting the question. I really struggle with recursion and it is kind of weird to explain when I come up with the solution :-).

This was my solution to keep updating the trace vector and compute the nth fibonacci:

else  
    trc=[trc n];
    a=n-1;
    [a trc]=fibo_trace(a-1,trc);
    [n trc]=fibo_trace(n-1,trc);
    f=n+a;
end

BR,

Carlos.

[Stephen23]

"I really struggle with recursion..."

Absolutely everyone struggles with recursion. I think you are doing really very well, to come up with that by yourself.

[Rayyan Ramrajkar]

Can you explain how trc knows whiich value is being called ?

Since we want to know which value function is calling for every recursive call, how does trc in input argument equates to that value in this line of code? Thank you

[a trc]=fibo_trace(a-1,trc);

[Carlos Rueda]

It might be a bit confusing and it is a while ago since I did this. But here some intuition:

The first recursive call assigns a new value to trc taking the current value of trc as an asgument.

The second recursive call assigns again a new value to trace taking as argument the trc value from the first recursive call. Maybe it would be more illustrative to rewrite the code like this:

else

trc=[trc n];

a=n-1;

[a trc1]=fibo_trace(a-1,trc);

[n trc2]=fibo_trace(n-1,trc1);

f=n+a;

end

You try it and tell me.

[Lusty Lloyd]

function [f, trace] = fibo_trace(n, v)
    if isempty(v)
        v = [];
    end
    v = [v n];
    if n <= 2
        f = 1;
    else
        [f1, v] = fibo_trace(n-2, v);
        [f2, v] = fibo_trace(n-1, v);
        f = f1 + f2;
    end
    trace = v;
end

Answer 2

[Rajith]

function [f, v] = fibo_trace(n,v)
    v(end+1) = n;
    if n == 1 || n == 2
        f = 1;
    else
        [f1, v] = fibo_trace(n-2,v); 
        [f2, v] = fibo_trace(n-1,v);
        f = f1+f2;
    end
end

Answer 3

[Divyanshu]

function [f, v] = fibo_trace(n,v)

v(end+1) = n;

if n == 1 || n == 2

f = 1;

else

[f1, v] = fibo_trace(n-2,v);

[f2, v] = fibo_trace(n-1,v);

f = f1+f2;

end

end