Calculate Fibonacci Series

 

This is one of the most asked question in interviews, calculating and printing Fibonacci series.

Let’s first try the iterative approach that is simple and prints all the Fibonacci series by passing the length.

Please note that we are starting the series from 0 (instead of 1).

public static voidFibonacci_Iterative(int len)

        {

            int a = 0, b = 1, c = 0;

            Console.Write(“{0} {1}”, a,b);

 

            for (int i = 2; i < len; i++)

            {

                c= a + b;

                Console.Write(” {0}”, c);

                a= b;

                b= c;

            }

       }

 

Test Results:

Input: Fibonacci_Iterative(9);

Output:

 

We can also use the recursive way to print the series against the length as below.

public static voidFibonacci_Recursive(int len)

        {

           Fibonacci_Rec_Temp(0, 1, 1, len);

       }

 

private static voidFibonacci_Rec_Temp(int a, int b, int counter,int len)

        {

            if (counter <= len)

            {

                Console.Write(“{0} “, a);

               Fibonacci_Rec_Temp(b, a + b, counter+1, len);

            }

       }

 

Here we have used two functions just to pass only the length as an input parameter. In the second method 4 parameters are required since we need to continue changing the variable’s position (in other words a -> b and b -> a + b).

We also need to increment the counter in each recursion call and to compare it with the length and continue the loop until it exceeds the length parameter. 

Test Results:

Input: Fibonacci_Recursive(11);

Output:

 

Calculate nth Fibonacci number:

Calculating the nth Fibonacci number is not difficult, we just need to pass the value with the right index.

We will first have a look at an iterative approach.

Here we are using an integer array to keep the Fibonacci numbers until n and returning the nth Fibonacci number.

public static int GetNthFibonacci_Ite(int n)

        {

            int number = n – 1; //Need to decrement by 1 since we are starting from 0

            int[] Fib = new int[number + 1];

            Fib[0]= 0;

            Fib[1]= 1;

 

            for (int i = 2; i <= number;i++)

            {

               Fib[i] = Fib[i – 2] + Fib[i – 1];

            }

            return Fib[number];

        }

 

Test Results:

Input: GetNthFibonacci_Ite(4);

Output:

 

We can also look for a recursive version of that. The only thing to consider is, here we need to pass a number less than 1 to get the nth Fibonacci number.

For example if we want the 8th Fibonacci number then we need to pass 8-1 (in other words 7) as an input (we can also create a pass-through method alternatively).

public static int GetNthFibonacci_Rec(int n)

        {

            if ((n == 0) || (n == 1))

            {

                return n;

            }

            else

                returnGetNthFibonacci_Rec(n – 1) + GetNthFibonacci_Rec(n – 2);

       }

 

 Test Results:

Input: GetNthFibonacci_Rec(8-1);

Output:

 

Please inform me of your comments/suggestions or if you have any better way to do it. J

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s