Finding the N'th number in the Fibonacci sequence

What is a Fibonacci Sequence
The Fibonacci sequence starts with the numbers 0 followed by 1. The subsequent number is the addition of the previous two numbers. Thus the Fibonacci sequence looks like below
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on.

Note : Generating the n’th number in Fibonacci sequence using recursion is very inefficient as we come across numerous overlapping sub-problems. A better idea is to use an iterative or dynamic programming approach.

Algorithm : Finding the n’th Fibonacci number
FibonacciNumber ( n )
1.   If n is 0 or 1
2.       return n
3.   Else return the sum of the previous two Fibonacci numbers.
4.       return FibonacciNumber ( n - 1 ) + FibonacciNumber ( n - 2 )

Program for recursively finding the N’th Fibonacci number 

def Fibonacci (n) :

    if n <= 1  :
       return n 

    return Fibonacci (n-1) + Fibonacci (n-2)
    
def main() :
    n = int(input("Finding n'th Fibonacci(n) number. Enter n : ")) 
    if n <= 1 : 
        print(n, end = ' ')
    else :
        print(int(Fibonacci(n)))

if __name__ == "__main__" :
    main()

Output

Finding n'th Fibonacci(n) number. Enter n : 10
55
Finding n'th Fibonacci(n) number. Enter n : 2
1
Finding n'th Fibonacci(n) number. Enter n : 11
89
Finding n'th Fibonacci(n) number. Enter n : 12
144

#include<iostream>

using namespace std;
typedef unsigned long long ULL;

ULL Fibonacci(ULL n) {

    if (n <= 1)
        return n;

    return (Fibonacci(n-1) + Fibonacci(n-2));
}

int main() {

    ULL n;
    cout << "Finding n'th Fibonacci(n) number. Enter n : ";
    cin >> n;
    cout << Fibonacci (n);
    return 0;
}

Output

Finding n'th Fibonacci(n) number. Enter n : 10
55
Finding n'th Fibonacci(n) number. Enter n : 1
1
Finding n'th Fibonacci(n) number. Enter n : 12
144

import java.util.Scanner;

class Fibo {

    public static long Fibonacci ( long n ) { 
        if ( n <= 1 ) { 
            return n;
        }
        return ( Fibonacci ( n - 1 ) + Fibonacci ( n - 2 ) );
    }   
    
    public static void main (String[] args) {
    
        long n;
        System.out.print( "Finding n'th Fibonacci(n) number. Enter n : " );
        Scanner sc = new Scanner ( System.in );
        n = sc.nextLong();
        System.out.println( Fibonacci ( n ) );
    }   
}

Output

Finding n'th Fibonacci(n) number. Enter n : 10
55
Finding n'th Fibonacci(n) number. Enter n : 1
1
Finding n'th Fibonacci(n) number. Enter n : 12
144

© 2019-2026 Algotree.org | All rights reserved.

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"The only way to do great work is to love what you do. - Steve Jobs"