Write a Java Program to print Fibonacci Series using Recursion.
Question Explanation
Fibonacci Series is a sequence of numbers where each number is the sum of the two preceding ones, typically starting with 0 and 1. The question tests a candidate's understanding of recursion, a fundamental programming concept where a function calls itself to solve smaller instances of the same problem. Interviewers often ask this to assess a candidate's ability to implement recursive algorithms effectively, which is crucial in many programming tasks. Additionally, understanding Fibonacci series can help in grasping concepts like dynamic programming and optimization techniques. It’s important to articulate the base cases correctly to avoid infinite recursion, which is a common pitfall. This question is relevant in various fields like software engineering, algorithm design, and data structures. Candidates should be prepared to discuss the time and space complexity of their solution, typically O(n) for recursion with memoization and O(2^n) for naive recursion. The Fibonacci sequence is not only a classic example in programming interviews but also has applications in financial modeling, computer graphics, and nature-related algorithms. Understanding it can demonstrate a solid grasp of algorithmic thinking and problem-solving skills.
Sample Answers
Example 1: Basic Recursive Approach
To print the Fibonacci series using recursion in Java, we can define a method that calculates the Fibonacci number at a given position. The base cases are when the position is 0 or 1, returning 0 and 1, respectively. For other positions, we recursively call the method for the two preceding positions. Here’s the code:
public class Fibonacci {
public static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
int count = 10; // Number of Fibonacci numbers to print
for (int i = 0; i < count; i++) {
System.out.print(fib(i) + " ");
}
}
}
In this example, the fib method calculates the Fibonacci number using recursion. The main method prints the first 10 Fibonacci numbers. While this approach is straightforward, it has a time complexity of O(2^n) due to repeated calculations, making it inefficient for larger values of n.
Example 2: Recursive Approach with Memoization
To optimize the Fibonacci calculation, we can use memoization, which stores previously computed Fibonacci numbers. This reduces the time complexity to O(n) while maintaining the recursive structure. Here’s how to implement it:
import java.util.HashMap;
import java.util.Map;
public class Fibonacci {
private static Map<Integer, Integer> memo = new HashMap<>();
public static int fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
int count = 10;
for (int i = 0; i < count; i++) {
System.out.print(fib(i) + " ");
}
}
}
In this code, we utilize a HashMap to store computed Fibonacci values. Before performing the calculation for fib(n), we check if the value is already in the memo. This significantly speeds up the process and is a great example of combining recursion with optimization techniques.
Example 3: Iterative Approach as Comparison
While recursion is a common approach, it’s also valuable to compare iterative solutions. An iterative method can be more efficient in terms of space. Here’s how to implement the Fibonacci series iteratively:
public class Fibonacci {
public static void main(String[] args) {
int count = 10;
int a = 0, b = 1;
System.out.print(a + " ");
for (int i = 1; i < count; i++) {
System.out.print(b + " ");
int next = a + b;
a = b;
b = next;
}
}
}
In this example, we use two variables to keep track of the last two Fibonacci numbers. The loop runs for the desired count, and we print each number in the sequence. This approach has a time complexity of O(n) and a space complexity of O(1), making it more efficient than the recursive methods, especially for large values.
Keywords
Ready to practice more questions?
Explore our collection of technical interview questions from top companies.
View All Questions