How to get fibonacci sequence using recursion?

Question

I am trying to find the fib sequence using recursion but my function keeps giving me an error.

function y = r_nFib(seq, n)
y = zeros(1,n);
for m = 1:n
    y(m) = r_nFib(m);
end
if seq == 0
    y = [0 y];
else
    y = [seq, seq, y];
function y = r_nFib(seq, n)
if n<3
   y(1:n) = 1;
else
    y(n) = r_nFib(n-2) + r_nFib(n-1);
end
    y = y(n);
end
end

n is the length of the fib sequence and seq is the starting number. If seq is 0 then this is how the sequence is going to start

y = [0 1 1 2 3 5 8] % first two number will be the 0 and 1

if seq is any thing other than 0, then

if seq = 2;

y = [2 2 4 6 10] % first two number will be the seq

How do I correct my function to give me the right answer. I have never used recursion and I am new to it. Any help would be really appreciated.

y = r_nFib(4,10)
y = [4 4 8 12 20 32 52 84 136 220];

Thank you.

Don't put local functions inside the main function; put it after the `end` of the main function. It still works and won't be visible to outside callers. — Setsu, Mar 27 '15 at 20:02
I still get an error saying Error using r_nFib (line 2) Not enough input arguments. Error in r_nFib (line 4) y(m) = r_nFib(m); — Jason Thapa, Mar 27 '15 at 20:10
By the way, to be pedantic the Fibonacci Sequence is _defined_ to have a starting pair of either `[0 1]` or `[1 1]`; any other starting pairs are Fibonacci-like but not strictly Fibonacci. The distinction is important because they have different properties (see [Lucas Number](http://en.wikipedia.org/wiki/Lucas_number)) — Setsu, Mar 27 '15 at 20:11
You get that because your function requires 2 input parameters but you only passed 1. If you want the second to be optional you need to explicitly implement that. See [this question](http://stackoverflow.com/questions/6764062/optional-arguments-in-matlab-functions) — Setsu, Mar 27 '15 at 20:18
Also, [nested functions](http://www.mathworks.com/help/matlab/matlab_prog/nested-functions.html#btfml3d) cannot be defined within `if` statements. Additionally, you can't define a nested or local function with the same name as the main function, so the second `r_nFib` needs a different name; although I don't think you need a second function once the control flow is correct. — TroyHaskin, Mar 27 '15 at 20:24

score 1 · Answer 1 · edited May 23 '17 at 10:24

Here is a solution that I typed up for matlab, explaining recursion:

A recursive method works by breaking a larger problem into smaller problems each time the method is called. This allows you to break what would be a difficult problem; a factorial summation, into a series of smaller problems.

Each recursive function has 2 parts:
1) The base case: The lowest value that we care about evaluating. Usually this goes to zero or one.

if (num == 1)
  out = 1;
end

2) The general case: The general case is what we are going to call until we reach the base case. We call the function again, but this time with 1 less than the previous function started with. This allows us to work our way towards the base case.

out = num + factorial(num-1);

This statement means that we are going to firstly call the function with 1 less than what this function with; we started with three, the next call starts with two, the call after that starts with 1 (Which triggers our base case!)

Once our base case is reached, the methods "recurse-out". This means they bounce backwards, back into the function that called it, bringing all the data from the functions below it!
It is at this point that our summation actually occurs.

Once the original function is reached, we have our final summation.

For example, let's say you want the summation of the first 3 integers. The first recursive call is passed the number 3.

  function [out] = factorial(num)
     %//Base case
     if (num == 1)
        out = 1;
     end
  %//General case
  out = num + factorial(num-1);

Walking through the function calls:

factorial(3); //Initial function call

//Becomes..
factorial(1) + factorial(2) + factorial(3) = returned value

This gives us a result of 6!

matlab - Clearer explanation of recursion

Konigwolf · Accepted Answer · 2015-03-27T21:33:29.403

1

function y = r_nFib(seq, n)

if length(seq) == 1
    if seq == 0
        seq = [0, 1];
    else
        seq = [seq, seq];
    end
end

if length(seq) >= n
    y = seq;
else
    y = r_nFib([seq (seq(end - 1) + seq(end))], n);
end

edited Mar 27 '15 at 21:33

answered Mar 27 '15 at 21:28

Konigwolf

26
3

How to get fibonacci sequence using recursion?

2 Answers2