You misunderstand Fibonacci numbers, at least in terms of the recursion.
The basic Fibonacci recursion, i.e.,
f(n) = f(n-1) + f(n-2)
refers to the index of the Fibonacci number. Thus, we have
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 3
etc. That is not what you are apparently computing in the code. It is NOT true that the last Fibonacci number less than or equal to the number x will satisfy the same recursion on x.
Anyway, the recursion as you have written it is a terrible way to compute Fibonacci numbers. The recursive scheme as you implement it will be extremely inefficient for large index. In fact, you won't even need to go that far before it bogs down your computer.
Why not just do it using a while loop? No recursive calls are needed at all.
function lfib = largefib(x)
% compute the largest fibonacci number <= x
% Code only works for positive values of x, even though
% the Fibonacci sequence can be extended for a
% negative index.
if x <= 1
lfib = 1;
return
end
fnminus2 = 0;
fnminus1 = 1;
fn = -inf;
while fn <= x
fn = fnminus1 + fnminus2;
fnminus2 = fnminus1;
fnminus1 = fn;
end
lfib = fnminus2;
The point is, by making this a simple direct loop, the computation will be O(log(n)) in time, where n is the Fibonacci index.
Finally, a by far easier way to solve this problem is to use the Binet formula for the Fibonacci numbers. Take the log, being careful in the mathematics. I.e., can you drop one of those terms in the Binet formula?
