MATLAB: Fibonacci function displaying issues

fibonacci

I created a function for a fibonacci number. I want it to display the largest fibonacci number that is less than or equal to the input. I currently have it set up to run and it will display the last number in the series. Any suggestions as to getting it to display the largest number less than or equal to n?

function f=lastfibonacci(n)
% Returns the largest fibonacci number that is less than or equal to n.
if n<=1;
    f=1;
else
    f=(lastfibonacci(n-1)+lastfibonacci(n-2));
end
end

Wanting:

Ex.: lastfibonacci(7)
ans= 5

Best Answer

If you choose to use recursion, you will have quite some time with this. I think it is better to use iteration, myself.

function F3 = lastfibonacci(n)
% Help, and need to check for n<1.
F1 = 1;
F2 = 1;
while F2<=n
    F3 = F2;
    F2 = F2 + F1; % The Fib number.
    F1 = F3;
end

Related Solutions

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

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?

MATLAB: Matlab confirm is input is not an array

n = input('Enter in a positive integer: ')
while n<0 | numel(n)>1 | fix(n)~=n
  n = input('Enter in a positive integer: ')
end

Best Answer

Related Solutions

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

MATLAB: Matlab confirm is input is not an array

Related Question