In this article, I’ll walk you through what a Fibonacci series is and how to write a Scala program to print a Fibonacci series of the total numbers specified by the user. We will do it in two different ways - iterative and recursive.
Let us start by first understanding what makes a Fibonacci series.
What is a Fibonacci series?
The Fibonacci series is a sequence of numbers where the sum of the two previous numbers becomes the next number of that series. The Fibonacci series starts with 0 and 1, and as per the definition, the third number in the sequence becomes 1 (0+1). The fourth number of the Fibonacci series is the sum of the 2nd and 3rd numbers, i.e., 1+1 = 2.
Mathematically, we can explain the Fibonacci series with the below formula, where X(i) represents an element at the i’th position.
X(i) = X(i-1) + X(i-2)
The following is the Fibonacci series:
0, 1, 1, 2, 3, 5, 8, 13, 21 ………
Let us now write Scala programs in two different ways, namely iteratively and recursively, to print the Fibonacci series.
Generate Fibonacci series Iteratively
Program
objectFibonacciextendsApp {
println("Please enter how many elements of fibonacci series you want to print")
val numberOfElements = scala.io.StdIn.readInt()
var firstElement = 0
var secondElement = 1
print(s"Fibonacci series for first ${numberOfElements} is : \n")
print(firstElement + " " + secondElement + " ")
for (i<-0 until numberOfElements-2 ) {
val nextElement = firstElement + secondElement
print(nextElement + " ")
firstElement = secondElement
secondElement = nextElement
}
}
Output
Please enter how many elements of fibonacci series you want to print
10
Fibonacci series for first 10 is :
0112358132134
Explanation
Let us understand the above program step-by-step:
- Initially, we printed a statement, which asks the user to enter the number of elements they want to have in the Fibonacci series.
- Later, we created a variable, numberOfElements, to receive the user input.
In order to get started with the Fibonacci series, we need to specify the first two elements of the series.
- We have created the first two elements as mutable variables var, because we will need to update the variables to find out the next element of the series incrementally.
- Next, we used the for loop to find out the next elements to run exactly the number of times as per user input. We subtracted the user input number by 2, considering we already have two elements called 0(first element) and 1(second element).
- Inside the loop, in every iteration, we calculated the next element of the series by adding the previous two elements and swapped the variables firstElement and secondElement to store the exact previous members of the series.
Generate Fibonacci series Recursively
With the recursive method, we will eliminate the use of the mutable variables since Scala recommends immutability . Also, since tail recursion is a better approach, we will try to write our algorithm in a tail-recursive manner rather than recursion.
While approaching a recursive solution to the Fibonacci problem, we should identify the below factors:
- Base Condition: The condition at which the program will come out of recursion to yield a result.
- Local variables: These variables will store the intermediate values at every recursive call in the stack.
As per the program, we can consider a counter that will exit, once it has recursively executed the desired number of iterations as per user input. Local variables will be the two initial values to compute the next value of the sequence.
With the above factors in mind, we already know how our recursive function should look like:
defcomputeFibonacci(counter: Int, firstElement: Int, secondElement: Int): Unit = {
// Base condition and computations
}
Let us add the computational details to complete the program.
Program
import scala.annotation.tailrec
objectFibonacciextendsApp {
println("Please enter how many elements of fibonacci series you want to print")
val numberOfElements = scala.io.StdIn.readInt()
@tailrec
defcomputeFibonacci(counter: Int, firstElement: Int, secondElement: Int): Unit = {
if(counter == 1)
print((firstElement + secondElement) + " ")
else {
print((firstElement+secondElement) + " ")
computeFibonacci(counter-1, secondElement, firstElement + secondElement)
}
}
var firstElement = 0
var secondElement = 1
print(s"Fibonacci series for first ${numberOfElements} is : \n")
print(firstElement + " " + secondElement + " ")
computeFibonacci(numberOfElements-2, firstElement, secondElement)
}
Output
Please enter how many elements of fibonacci series you want to print
10
Fibonacci series for first 10 is :
0112358132134
Explanation
In the above program, we have used @tailrec (tail recursion annotation) to explicitly tell the compiler that it is a tail recursive method and it should do the required optimizations implicitly.
- We specified the base condition as when the counter reaches 1, the program should terminate the recursion calls.
- Inside the recursive method, computeFibonacci , we used the same swapping principle .
- The variable values of firstElement and secondElement are stored in the recursion stack local variables on each recursive call.
- At each computation of nextElement, we printed the result on the console.
- We already printed the first and second element because computeFibonacci will calculate the next element, given, it already know the previous two elements of the series.
- Since we have now written our recursive implementation to calculate fibonacci series, we need to make the initial call as per our logic with the seed values(base condition counter and first two values of series). Deciding the seed values is important for the recursion to act in a way that it run the desired number of times.
- In the last line, we made the first call to computeFibonacci with the maximum count for which we want to do a recursive call. Hence counter value becomes “ numberOfElements - 2 ” and the two initial values become firstElement:0 and secondElement:1 which are the known initial members of the series..
Conclusion
This was all about a Scala program to display the Fibonacci series. Once you understand what a Fibonacci series is, it becomes easy to implement a program for it. However, you must have a good grasp of the for loop, recursion, and tail recursion.
I have explained writing a Scala program for the Fibonacci series using both iterative and recursive approaches. I recommend you try these programs on your system and understand them in a much better way.
Happy Coding!
Leave a Comment on this Post