Divide and conquer

Fibonacci numbers

Pinterest LinkedIn Tumblr

Fibonacci number is a number that start with one or zero and next number is equal to the sum of previous two numbers. Ex F (0) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Sample Input and Output

The first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

Example

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

source Code

package com.dsacode.Algorithm.divideconquer;
 
public class Fibonacci {
 
    public static int recursiveFibonacci(int num){
        if(num==1 || num==2)
            return 1;
        else
            return recursiveFibonacci(num-1) + recursiveFibonacci(num-2);
         
    }
     
 
     public static int iterFibonacci(int number){
           if(number == 1 || number == 2){
               return 1;
           }
             
            int fibo1=1, fibo2=1, fibonacci=1;
             
            for(int i= 3; i <= number; i++){
                fibonacci = fibo1 + fibo2;
                fibo1 = fibo2;
                fibo2 = fibonacci;
               
            }
            return fibonacci;
        }  
       
    public static void main(String[] args) {
 
        int numberOfFib =10;
         
        System.out.print("Print the first " + numberOfFib + " Fibonacci numbers using iterative funcation:");
        for(int i=1;i <= numberOfFib;i++){
            System.out.print(iterFibonacci(i) +" ");
        }
 
         
        System.out.print(" \nPrint the first " + numberOfFib + " Fibonacci numbers using recursive funcation:");
        for(int i=1;i <= numberOfFib;i++){
            System.out.print(recursiveFibonacci(i) +" ");
        }
 
         
    }
 
}

Output

Print the first 10 Fibonacci numbers using iterative funcation:1 1 2 3 5 8 13 21 34 55 
Print the first 10 Fibonacci numbers using recursive funcation:1 1 2 3 5 8 13 21 34 55

Algorithm Explanation

Get the number of Fibonacci numbers to display.
Use recursive function to decide the fib number. If the number is 1 or 2, return 1.
Else call recursively with recursiveFibonacci(num-1) + recursiveFibonacci(num-2)

Reference

  1. http://en.wikipedia.org/wiki/Fibonacci_number
  2. https://www.mathsisfun.com/numbers/fibonacci-sequence.html
  3. http://mathworld.wolfram.com/FibonacciNumber.html

Write A Comment