Fibonacci Series Program in Python, C and Java

What You Will Learn

• The problem statement
• What is the Fibonacci series?
• Fibonacci program using a loop
• Fibonacci program using recursion
• Other ways: no third variable, up to a limit, memoization
• How big can the terms get?
• Fibonacci and the golden ratio
• Common mistakes, practice questions and FAQ

Problem Statement

Write a program to display the terms of a Fibonacci series.

The user enters how many terms they want. The program prints that many terms of the Fibonacci series, separated by spaces. The interactive tool above accepts 1 to 30 terms.

What Is the Fibonacci Series?

The Fibonacci series is a sequence of numbers in which every term, starting from the third, is the sum of the two terms before it. The series starts with 0 and 1.

Rule: F(0) = 0, F(1) = 1, and F(n) = F(n − 1) + F(n − 2) for n ≥ 2.

Some books start the series with 1, 1 instead of 0, 1. The programs in this post start with 0, which is the version used in most school syllabuses and exams. The first 15 terms are:

Fibonacci Program Using a Loop

The loop method is the best way to write the program. It remembers only the last two terms, in variables a and b, and builds the next term from them.

Logic:

• Read n, the number of terms.
• Start with a = 0 and b = 1, the first two terms.
• Repeat n times: print a, calculate c = a + b, then move forward with a = b and b = c.

The order of the three assignments is important. If you write a = b before calculating c, the old value of a is lost.

Python program

n = int(input("Enter number of terms: "))
a = 0
b = 1
for i in range(n):
    print(a, end=" ")
    c = a + b
    a = b
    b = c
print()

#include <stdio.h>
int main() {
    int n;
    printf("Enter number of terms: ");
    scanf("%d", &n);
    int a = 0, b = 1, c;
    for (int i = 0; i < n; i++) {
        printf("%d ", a);
        c = a + b;
        a = b;
        b = c;
    }
    printf("\n");
    return 0;
}

import java.util.Scanner;
public class Fibonacci {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of terms: ");
        int n = sc.nextInt();
        int a = 0, b = 1, c;
        for (int i = 0; i < n; i++) {
            System.out.print(a + " ");
            c = a + b;
            a = b;
            b = c;
        }
        System.out.println();
    }
}

Sample output:

Enter number of terms: 10
0 1 1 2 3 5 8 13 21 34

Another run:

Enter number of terms: 1
0

Dry run for n = 7:

The program prints 0 1 1 2 3 5 8.

Fibonacci Program Using Recursion

The definition of the series is itself recursive: F(n) is made from F(n − 1) and F(n − 2). So we can turn the definition directly into a function that calls itself.

Logic:

• Base case: if n is 0 or 1, return n.
• Otherwise return fib(n - 1) + fib(n - 2).
• In main, call fib(i) for i from 0 to n − 1 and print each result.

Python program

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
n = int(input("Enter number of terms: "))
for i in range(n):
    print(fib(i), end=" ")
print()

#include <stdio.h>
int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}
int main() {
    int n;
    printf("Enter number of terms: ");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        printf("%d ", fib(i));
    }
    printf("\n");
    return 0;
}

import java.util.Scanner;
public class Fibonacci {
    static int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of terms: ");
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            System.out.print(fib(i) + " ");
        }
        System.out.println();
    }
}

Sample output:

Enter number of terms: 8
0 1 1 2 3 5 8 13

Recursion is neat, but it is slow. Every call to fib(n) starts two more calls, and the same values are calculated again and again. For example, fib(3) is calculated twice while finding fib(5). The number of function calls needed for fib(k) grows almost as fast as the series itself:

Finding fib(29) alone needs 1,664,079 calls, and the loop version would need only 29 additions. This is why we prefer the loop for printing a series, and use recursion mainly to show how recursion works.

Other Ways to Write the Fibonacci Program

Method 3: Without a third variable

You can drop the variable c. Here a is the term to print and b is the term that came before a. The series can be extended backwards, so before 0 comes 1 (because 1 + 0 = 1). That is why we start with a = 0 and b = 1 again.

• a = a + b turns a into the next term.
• b = a - b turns b into the old a, which is now the previous term.

Python program without a third variable

n = int(input("Enter number of terms: "))
a = 0
b = 1
for i in range(n):
    print(a, end=" ")
    a = a + b
    b = a - b
print()

#include <stdio.h>
int main() {
    int n;
    printf("Enter number of terms: ");
    scanf("%d", &n);
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        printf("%d ", a);
        a = a + b;
        b = a - b;
    }
    printf("\n");
    return 0;
}

import java.util.Scanner;
public class Fibonacci {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of terms: ");
        int n = sc.nextInt();
        int a = 0, b = 1;
        for (int i = 0; i < n; i++) {
            System.out.print(a + " ");
            a = a + b;
            b = a - b;
        }
        System.out.println();
    }
}

Sample output:

Enter number of terms: 8
0 1 1 2 3 5 8 13

Method 4: Python tuple swap

Python can assign both variables at the same moment, so no temporary variable is needed. The right side is calculated first, and then both names are updated.

n = int(input("Enter number of terms: "))
a, b = 0, 1
for i in range(n):
    print(a, end=" ")
    a, b = b, a + b
print()

Method 5: Print the first two terms separately

Some textbooks print 0 and 1 outside the loop, and use the loop only to calculate the remaining terms from the third onwards. The loop then runs from 2 to n − 1. The checks n >= 1 and n >= 2 make the program safe when the user asks for only one or two terms.

n = int(input("Enter number of terms: "))
if n >= 1:
    print(0, end=" ")
if n >= 2:
    print(1, end=" ")
a = 0
b = 1
for i in range(2, n):
    c = a + b
    print(c, end=" ")
    a = b
    b = c
print()

Method 6: Print terms up to a limit

Instead of asking for the number of terms, you may be asked to print all Fibonacci numbers up to a limit, such as 100. Use a while loop that stops when a becomes bigger than the limit.

Python program (up to a limit)

limit = int(input("Enter the limit: "))
a = 0
b = 1
while a <= limit:
    print(a, end=" ")
    a, b = b, a + b
print()

#include <stdio.h>
int main() {
    int limit;
    printf("Enter the limit: ");
    scanf("%d", &limit);
    int a = 0, b = 1, c;
    while (a <= limit) {
        printf("%d ", a);
        c = a + b;
        a = b;
        b = c;
    }
    printf("\n");
    return 0;
}

Sample output:

Enter the limit: 100
0 1 1 2 3 5 8 13 21 34 55 89

Method 7: Recursion with memoization

Memoization fixes the main problem of recursion. The function saves every answer in a dictionary, so each value is calculated only once, and the number of calls drops from exponential to linear.

memo = {}
def fib(n):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
n = int(input("Enter number of terms: "))
for i in range(n):
    print(fib(i), end=" ")
print()

Sample output:

Enter number of terms: 10
0 1 1 2 3 5 8 13 21 34

How Big Can the Terms Get?

The series grows fast. In C and Java, an int holds values only up to 2,147,483,647. The largest Fibonacci number that fits is F(46) = 1,836,311,903. The next term, F(47) = 2,971,215,073, is too big, so the program would print a wrong (negative) number. A long in Java or a long long in C can go up to F(92) = 7,540,113,804,746,346,429. Python has no such limit, and its integers grow as large as memory allows.

For school programs, asking for 20 or 30 terms is always safe. The interactive tool above stops at 30 terms for the same reason: the numbers stay short and easy to read.

Fibonacci and the Golden Ratio

If you divide a term by the term before it, the answer comes closer and closer to the golden ratio, about 1.618034.

Fibonacci numbers also appear in nature, for example in the number of petals of some flowers and in the spirals of sunflower heads and pine cones.

Common Mistakes

1. Updating a and b in the wrong order. If you write a = b and then b = a + b, you use the already changed a. Calculate c first, or use the tuple swap in Python.
2. Printing b instead of a. With a = 0 and b = 1, printing b makes the series start from 1 and miss the 0.
3. Wrong loop count. The loop must run exactly n times for n terms. Starting the loop at 2 without printing the first two terms separately gives n − 2 terms.
4. Missing base case in recursion. Without if n <= 1: return n the function never stops, and the program crashes with a stack overflow or a RecursionError.
5. Using recursion for large n. The plain recursive version becomes painfully slow after about 35 to 40 terms. Use a loop or memoization.
6. Using int for big terms. After F(46) an int overflows in C and Java. Switch to long long or long.

Practice Questions

1. Print the Fibonacci series up to 500.
2. Print the sum of the first n Fibonacci numbers.
3. Print only the even Fibonacci numbers below 1000.
4. Check whether a number entered by the user is a Fibonacci number.
5. Print the nth Fibonacci number without printing the whole series.
6. Start the series from two numbers entered by the user, for example 3 and 7. Hint: only the starting values of a and b change.

Frequently Asked Questions

What is the Fibonacci series?

It is a series in which each term is the sum of the previous two terms. It starts 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

How do you write a Fibonacci series program in Python?

Set a = 0 and b = 1. In a loop that runs n times, print a, calculate c = a + b, then set a = b and b = c.

Which is better, a loop or recursion?

The loop is faster and uses almost no memory. Recursion is shorter and matches the definition, but it repeats a lot of work. Use a loop for printing a series, and use recursion to learn how recursion works.

Does the Fibonacci series start from 0 or 1?

Most school syllabuses start from 0, giving 0, 1, 1, 2, 3. Some books start from 1, giving 1, 1, 2, 3. Both are accepted, but you should follow your own textbook.

What is the time complexity of the Fibonacci program?

The loop version takes O(n) time and O(1) extra space. The plain recursive version takes about O(2ⁿ) time. The memoized version takes O(n) time.

How do I print the Fibonacci series without a third variable?

Use a = a + b followed by b = a - b, or in Python write a, b = b, a + b.

How do I print the Fibonacci series up to a given number?

Use a while loop with the condition a <= limit instead of a for loop that counts terms.

Why does my C or Java Fibonacci program print negative numbers?

An int overflowed. The largest Fibonacci number that fits in a 32-bit int is F(46) = 1,836,311,903. Use long long in C or long in Java for larger terms.

Why is recursive Fibonacci so slow?

Each call makes two more calls and the same values are calculated many times. The number of calls roughly multiplies by 1.6 for each extra term.