CODEWITHSUNDEEP
matlabrecursionfibonacci
Jason Thapa
Jason Thapa

Reputation: 123

How to get fibonacci sequence using recursion?

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.

Upvotes: 0

Views: 488

Answers (2)

Konigwolf
Konigwolf

Reputation: 26

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

Upvotes: 1

Evan Bechtol
Evan Bechtol

Reputation: 2865

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

Upvotes: 1

Related Questions