Profiling of inefficient recursive Fibonacci series function
17 views (last 30 days)
Show older comments
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:
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/469527/image.png)
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 Comments
Accepted Answer
Stephen23
on 23 Dec 2020
Edited: Stephen23
on 23 Dec 2020
Perhaps something like this:
[val,vec] = fibo(6)
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 Comments
Lusty Lloyd
on 13 Mar 2023
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
More Answers (2)
Rajith
on 17 Dec 2023
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
0 Comments
Divyanshu
on 28 Jul 2024
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
0 Comments
See Also
Categories
Find more on Loops and Conditional Statements in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!