How do i return the largest Fibonacci number that is less than or equal to x?

I wrote a recursive code to get the fibonacci number, but I need to get the fibonacci value that is less than or equal to x. For instance, lastfibonacci(7) ans = 5 Here's my code:

function n= lastfibonacci2(x)
if x==0||x==1
    n = x;
else
    n=lastfibonacci2(x-1)+lastfibonacci2(x-2);
end
end

I was trying to figure out a way to stop the else statement when n<=1 && n<=x, but every time I try to make a statement it doesnt give the right value.

Answer 1

[John D'Errico]

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?

[Mohannad Abboushi]

Awesome, can you explain how the while works exactly though? I am a little confused with that.

Answer 2

[Walter Roberson]

I recommend that you do not use recursion for this. Instead, loop forward from [0, 1] until you find that the number is > x, at which point you take the previous one.