Write a Java Program to print Fibonacci Series using Recursion.
Short Answer
To print the Fibonacci series using recursion in Java, define a method that calculates the Fibonacci number at a given position. Set base cases for positions 0 and 1, returning 0 and 1 respectively. For other positions, recursively call the method for the two preceding positions and sum their results.
What a Strong Answer Covers
- Define a recursive method for Fibonacci numbers.
- Set base cases for n <= 1 to return n.
- Recursively call for fib(n-1) + fib(n-2).
- Use a loop in main to print the series.
- Consider memoization for optimization.
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.
Why Interviewers Ask This Question
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.
Keywords
Related Interview Questions
Ready to practice more questions?
Explore our collection of technical interview questions from top companies.
View All Questions