Programs to display the n th fibonacci number have been shown here. For example if $n = 7$, we get the seventh fibonacci number i.e. $8$. The algorithm, pseudocode and time complexity of the program have also been given.
Page content(s):
4. Program & Output: Iterative approach
5. Program & Output: Recursive approach
Additional content(s):
1. Algorithm to display N th fibonacci
1. Take term no n as input.
2. If n = 1 return 0 as first fibonacci and exit program
3. If n = 2 return 1 as first fibonacci and exit program
4. Intialize a counter variable say count = 2
5. Assign the first two fibonacci numbers to variables a, b i.e. a = 0 and b = 1
6. Perform t = a + b
7. Perform a = b and b = t
8. Perform count = count + 1.
9. If count = n, display t as n th fibonacci and exit program else go to step 6
2. Pseudocode to display N th fibonacci
Input : Index of the term $n$
Output : $n$ th fibonacci number
1.Procedure nthFibonacci($n$):
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.End Procedure
3. Time complexity to display N th fibonacci
Time Complexity: O(n)
Where n is the index of the term in the fibonacci sequence.
4. Program & output to display N th fibonacci using iteration
This section covers the C, C++, Java, Python and C# programs to display the n th fibonacci number using iteration.
4.1. C Program & output to display N th fibonacci using iteration
/********************************** alphabetacoder.com C program to display N th fibonacci number using iteration ***********************************/ #include <stdio.h> int main() { // declare variables int n, count = 0, a, b, t; // take input of the term no printf("Enter the term no. = "); scanf("%d", & n); // intialize the first two number of the sequence a = 0; b = 1; // if first fibonacci if (n == 1) printf("Fibonacci no %d is %d", n, a); // if second fibonacci else if (n == 2) printf("Fibonacci no %d is %d", n, b); // except first and second fibonacci else if (n > 2) { // assign value count = 2; while (count < n) { // calculate next fibonacci t = a + b; //assign values for next iteration a = b; b = t; // increment the counter count = count + 1; } // display n th fibonacci printf("Fibonacci no %d is %d", n, t); } else printf("Invalid input!"); return 0; }
Output
Case 1:
Enter the term no. = 20
Fibonacci no 20 is 4181
Case 2:
Enter the term no. = 2
Fibonacci no 2 is 1
4.2. C++ Program & output to display N th fibonacci using iteration
/******************************** alphabetacoder.com C++ program to display N th fibonacci number using iteration *********************************/ #include <iostream> using namespace std; int main() { // declare variables int n, count = 0, a, b, t; // take input of the term no cout << "Enter the term no. = "; cin >> n; // intialize the first two number of the sequence a = 0; b = 1; // if first fibonacci if (n == 1) cout << "Fibonacci no " << n << " is " << a; // if second fibonacci else if (n == 2) cout << "Fibonacci no " << n << " is " << b; // except first and second fibonacci else if (n > 2) { // assign value count = 2; while (count < n) { // calculate next fibonacci t = a + b; //assign values for next iteration a = b; b = t; // increment the counter count = count + 1; } // display n th fibonacci cout << "Fibonacci no " << n << " is " << t; } else cout << "Invalid input!"; return 0; }
Output
Case 1:
Enter the term no. = 20
Fibonacci no 20 is 4181
Case 2:
Enter the term no. = 2
Fibonacci no 2 is 1
4.3. Java Program & output to display N th fibonacci using iteration
/********************************** alphabetacoder.com Java program to display N th fibonacci number using iteration ***********************************/ import java.util.Scanner; public class Main { public static void main(String[] args) { // declare variables int n, count = 0, a, b, t = 0; // declare instance of Scanner class Scanner sc = new Scanner(System.in); // take input of the term no System.out.print("Enter the term no. = "); n = sc.nextInt(); // intialize the first two number of the sequence a = 0; b = 1; // if first fibonacci if (n == 1) System.out.println("Fibonacci no " + n + " is " + a); // if second fibonacci else if (n == 2) System.out.println("Fibonacci no " + n + " is " + b); // except first and second fibonacci else if (n > 2) { // assign value count = 2; while (count < n) { // calculate next fibonacci t = a + b; //assign values for next iteration a = b; b = t; // increment the counter count = count + 1; } // display n th fibonacci System.out.println("Fibonacci no " + n + " is " + t); } else System.out.println("Invalid input!"); } }
Output
Case 1:
Enter the term no. = 20
Fibonacci no 20 is 4181
Case 2:
Enter the term no. = 2
Fibonacci no 2 is 1
4.4. Python Program & output to display N th fibonacci using iteration
#*********************************** # alphabetacoder.com #Python program to display N th #fibonacci number using iteration #*********************************** # take input of the term no n = int(input("Enter the term no. = ")) # intialize the first two number of the sequence a = 0 b = 1 # if first fibonacci if n == 1: print("Fibonacci no ",n ,"is ",a) # if second fibonacci elif n == 2: print("Fibonacci no ",n ,"is ",b) # except first and second fibonacci elif n > 2: # assign value count = 2 while count < n: # calculate next fibonacci t = a + b # assign values for next iteration a = b b = t # increment the counter count = count + 1 # display n th fibonacci print("Fibonacci no ",n ,"is ",t) else: print("Invalid input!")
Output
Case 1:
Enter the term no. = 20
Fibonacci no 20 is 4181
Case 2:
Enter the term no. = 2
Fibonacci no 2 is 1
4.5. C# Program & output to display N th fibonacci using iteration
/*********************************** alphabetacoder.com C# program to display N th fibonacci number using iteration ************************************/ using System; namespace NthFibonacci { class Program { static void Main(string[] args) { // declare variables int n, count = 0, a, b, t = 0; //take input of the number upto which // natural numbers will be printed Console.Write("Enter the term no. = "); n = Convert.ToInt32(Console.ReadLine()); // intialize the first two number of the sequence a = 0; b = 1; // if first fibonacci if (n == 1) Console.Write("Fibonacci no " + n + " is " + a); // if second fibonacci else if (n == 2) Console.Write("Fibonacci no " + n + " is " + b); // except first and second fibonacci else if (n > 2) { // assign value count = 2; while (count < n) { // calculate next fibonacci t = a + b; //assign values for next iteration a = b; b = t; // increment the counter count = count + 1; } // display n th fibonacci Console.Write("Fibonacci no " + n + " is " + t); } else Console.Write("Invalid input!"); // wait for user to press any key Console.ReadKey(); } } }
Output
Case 1:
Enter the term no. = 20
Fibonacci no 20 is 4181
Case 2:
Enter the term no. = 2
Fibonacci no 2 is 1
5. Program & output to display N th fibonacci using recursion
This section covers the C, C++, Java, Python and C# programs to display the n th fibonacci number using recursion.
5.1. C Program & output to display N th fibonacci using recursion
/********************************** alphabetacoder.com C program to display N th fibonacci number using recursion ***********************************/ #include <stdio.h> // recursive function to // find nth fibonacci int fibonacci(int n) { if (n == 1) return 0; if (n == 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2); } int main() { // declare variables int n; // take input of the term no printf("Enter the term no. = "); scanf("%d", & n); // find fibonacci if (n >= 1) { // display n th fibonacci // by calling the function printf("Fibonacci no %d is %d", n, fibonacci(n)); } else printf("Invalid input!"); return 0; }
Output
Case 1:
Enter the term no. = 7
Fibonacci no 7 is 8
Case 2:
Enter the term no. = 15
Fibonacci no 15 is 377
5.2. C++ Program & output to display N th fibonacci using recursion
/******************************** alphabetacoder.com C++ program to display N th fibonacci number using recursion *********************************/ #include <iostream> using namespace std; // recursive function to // find nth fibonacci int fibonacci(int n) { if (n == 1) return 0; if (n == 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2); } int main() { // declare variables int n; // take input of the term no cout << "Enter the term no. = "; cin >> n; // find fibonacci if (n >= 1) { // display n th fibonacci // by calling the function cout << "Fibonacci no " << n << " is " << fibonacci(n); } else cout << "Invalid input!"; return 0; }
Output
Case 1:
Enter the term no. = 7
Fibonacci no 7 is 8
Case 2:
Enter the term no. = 15
Fibonacci no 15 is 377
5.3. Java Program & output to display N th fibonacci using recursion
/******************************** alphabetacoder.com Java program to display N th fibonacci number using recursion *********************************/ import java.util.Scanner; public class Main { // recursive function to // find nth fibonacci public static int fibonacci(int n) { if (n == 1) return 0; if (n == 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2); } public static void main(String[] args) { // declare variables int n; // declare instance of Scanner class Scanner sc = new Scanner(System.in); // take input of the term no System.out.print("Enter the term no. = "); n = sc.nextInt(); // find fibonacci if (n >= 1) { // display n th fibonacci // by calling the function System.out.println("Fibonacci no " + n + " is " + fibonacci(n)); } else System.out.print("Invalid input!"); } }
Output
Case 1:
Enter the term no. = 7
Fibonacci no 7 is 8
Case 2:
Enter the term no. = 15
Fibonacci no 15 is 377
5.4. Python Program & output to display N th fibonacci using recursion
#********************************* # alphabetacoder.com #Python program to display N th #fibonacci number using recursion #********************************* # recursive function to # find nth fibonacci def fibonacci(n): if n == 1: return 0 if n == 2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) def main(): # take input of the term no n = int(input("Enter the term no. = ")) # find fibonacci if n >= 1: # display n th fibonacci # by calling the function print("Fibonacci no" , n , "is", fibonacci(n)) else: print("Invalid input!") # driver code # call main() main()
Output
Case 1:
Enter the term no. = 7
Fibonacci no 7 is 8
Case 2:
Enter the term no. = 15
Fibonacci no 15 is 377
5.5. C# Program & output to display N th fibonacci using recursion
/******************************* alphabetacoder.com C# program to display N th fibonacci number using recursion *********************************/ using System; namespace NthFibonacci { class Program { // recursive function to // calculate fibonacci number static int fibonacci(int n) { if (n == 1) return 0; if (n == 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2); } static void Main(string[] args) { // declare variables int n; // take input of the index // of the fibonacci number Console.Write("Enter the term no. = "); n = Convert.ToInt32(Console.ReadLine()); // find fibonacci if (n >= 1) { // display n th fibonacci // by calling the function Console.WriteLine("Fibonacci no " + n + " is " + fibonacci(n)); } else Console.WriteLine("Invalid input!"); // wait for user to press any key Console.ReadKey(); } } }
Output
Case 1:
Enter the term no. = 7
Fibonacci no 7 is 8
Case 2:
Enter the term no. = 15
Fibonacci no 15 is 377