# Matlab recursion (error in book?)

1. Nov 11, 2012

### Nano-Passion

This is what my book gives for recursion of fibonacci sequence (matlab coding).

function res = fib(n)
if n == 1;
res = 0;
elseif n == 2
res = 1;
else
res = fib(n-1) + fib(n-2);
end

Am I mistaken or this doesn't work for fib(3)? Keep in mind I am still learning about recursion.

>> fib(3)
res = fib(2)+fib(1)
fib(1) = 0. fib(2) = 1

therefore fib (3) = 1+0 = 1

fib(3) should be 2.

2. Nov 11, 2012

### chiro

Hey Nano-Passion.

I think this is an issue with semantics and definition as opposed to the algorithm itself being wrong.

It seems that this code is defining the sequence as the fibonacci sum of n individual terms with the first term being 0 and the second term being 1, so f(1) = 0, f(2) = 1 and f(n) = f(n-2) + f(n-1) for n > 2.

I've seen the series start with the terms 1 and 1 for the value of the first two terms as well which doesn't affect the rest of the series, and personally I think it makes more sense to do it this way (instead of 0,1) so in this case, you would have your definition of f(3) = 2 instead of f(3) = 1.

So while I side with you, it is just a matter of interpretation of what the initial values should be.

3. Nov 11, 2012

### Nano-Passion

Hey Chiro, thanks for the reply.

I'm a bit unclear here, can you elaborate or reword what you have stated please.

4. Nov 11, 2012

### chiro

Basically you can have a series that goes 0,1,1,2,3,5,8,.... or you can have 1,1,2,3,5,8.

The first one starts with 0,1 as two initial values and the second starts with 1,1 as two initial values.

Both produce the same sequence after the 1,1 case but the 2nd one is a subset of the 1st.

To me the 1st one doesn't make much sense anyway, but algorithmically they do produce the same series after the 1,1 point.

5. Nov 11, 2012

### Nano-Passion

Thanks for your time.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook