Profiling of inefficient recursive Fibonacci series function

Question

Carlos Rueda 2020-12-23

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/701197-profiling-of-inefficient-recursive-fibonacci-series-function

回答： Divyanshu 2024-7-28

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Stephen23 2020-12-23

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/701197-profiling-of-inefficient-recursive-fibonacci-series-function#answer_583037

编辑：Stephen23 2020-12-23

在 MATLAB Online 中打开

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 :)

5 个评论
显示 3更早的评论隐藏 3更早的评论

Carlos Rueda 2021-8-13

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 2023-3-13

在 MATLAB Online 中打开

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 2023-12-17

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/701197-profiling-of-inefficient-recursive-fibonacci-series-function#answer_1372962

在 MATLAB Online 中打开

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