CodingGyan

N-th Fibonacci Number

medium Series and Sequences

Problem

Read n and print the n-th Fibonacci number. The numbers start with F0 = 0 and F1 = 1, and every other number is the sum of the two numbers before it.

Constraints

  • 0 <= n <= 70 (the plain recursion is only practical for n <= 35)

Examples

Input

10

Output

55

Solutions

Brute forceTime O(2^n)Space O(n)

The definition is copied directly into code. It is easy to read, but the same values are calculated again and again, so the time grows very fast (about 1.6 times for each step).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Find the n-th Fibonacci number.
 * Input   : One integer n (n >= 0).
 * Output  : The n-th Fibonacci number (F0 = 0, F1 = 1).
 * Approach: Call the method for n - 1 and n - 2 (recursion).
 * Time    : O(2^n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method receives n and returns the n-th Fibonacci number. It calls itself for smaller values.
    static long fibonacci(int n) {
        // Step 1: The first two numbers are known: F0 = 0 and F1 = 1. This stops the recursion.
        if (n < 2) {
            return n;
        }

        // Step 2: Every other number is the sum of the two numbers before it.
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        System.out.println(fibonacci(n));
    }
}
Hints (2)
  1. What is the answer for n = 0 and n = 1?
  2. How many times is fibonacci(3) calculated when you ask for fibonacci(6)?

Try these next