Fibonacci Series in Java Using Recursion

In a Fibonacci Series, every number (except the first two numbers) is the sum of the previous two numbers. The mathematical formula for a Fibonacci series is:

$F(n) = F(n - 1) + F(n - 2)$

Here, F(n) represents the $n^{th}$ Fibonacci number.

In Java, we can use different techniques like recursion and memoization to create a Fibonacci series. To know more about how to print Fibonacci Series in Java using all the methods visit Fibonacci Series in Java

Let us take a look at a few examples to understand how we can create the Fibonacci series using recursion.

Fibonacci Series Using recursion in Java

To calculate the Fibonacci Series using recursion in Java, we need to create a function so that we can perform recursion. This function takes an integer input. The function checks whether the input number is 0, 1, or 2, and it returns 0, 1, or 1(for 2nd Fibonacci), respectively, if the input is any one of the three numbers.

If the input is greater than 2, the function calls itself recursively for the previous values until the value of the input variable becomes less than or equal to 2. So if the function receives an integer n as input, it will return the $nth$ Fibonacci number. To print the Fibonacci series, we will call this function to compute each Fibonacci number.

Output of the program:

In the above example, we defined a recursive function fibRecursion to get nth Fibonacci number and call it repeatedly (for i = 0 to i = 8) in order to create a Fibonacci series of length 9.

Time And Space Complexity

The time complexity of the recursive approach to solving the Fibonacci series is $O(2^n)$ i.e. exponential time. The space complexity of the recursive method is O(n), if we consider the recursive stack.

Exponential time complexity is extremely inefficient. It would take too long to calculate the Fibonacci series of a huge length using the recursive method. To solve this problem, we can use the memoization technique to create the Fibonacci Series. This technique is much faster than the recursive method.

Fibonacci Number Using Memoization in Java

Memoization is a programming technique used to improve the performance of recursion programs. In this technique, the result of the previous calculation is stored (cached) and reused. In the previous approach, we calculated each Fibonacci number separately. But, in this approach, we will use the previous results to calculate the current Fibonacci number. So, if we have calculated the Fibonacci of a number, we can reuse it without doing the calculation again.

In the previous approach, we calculated each Fibonacci number separately, but in this approach, we are going to use our previous results to calculate the current number.

Memoization can be done using HashMaps.

Output of the program:

In the above example, we created a function fibMemoize that uses memoization to calculate the Fibonacci number. In this function, we first checked if the variable n was 0 or 1. If n was 0, we returned 0, and if n was 1, we returned 1. If $n^{th}$ Fibonacci number was stored in the hashmap, we directly used its value to get the desired Fibonacci number. In case n was not stored, we calculate the Fibonacci value by calling the function for the previous two Fibonacci values, then stored this value into the hashmap, and finally return it to get our answer.

Time And Space Complexity

The time complexity of the memoization approach to calculate the Fibonacci series is O(n). The space complexity of this approach is O(n) as well.

Unlock the power of Dynamic Programming and take your coding skills to the next level – Enroll in our Dynamic Programming Certification Course now!