08: Coding Scala Way – Recursion & Higher Order Function

Example #20: nth Fibonacci number

Q1 What is wrong with the following recursive approach to compute the nth Fibonacci number?
A1 It “hangs” for the larger values of “n” like 50.

Q2 How about using an iterative approach as shown below?

A2 The iterative approach uses mutable variables as shown above like “a” and “b”. Functional programming, by its very nature, encourages you to write thread-safe code. Immutability is key to writing thread-safe code. Immutable code can be easily parallelized. Recursion promotes immutability, but in this scenario normal recursion is not efficient.

Q3 How can we then use recursion, which promotes immutability to fix the above issue with the code hanging?
A3Tail recursion” to the rescue.

Example #21: Higher Order Function

Here is a very simple Scala code without using any unit testing frameworks to test the above Fibonacci number code.

Q4 What if you want to test all three functions that demonstrated naive, looping, and tail recursion without having to copy the contents of the “test” method 3 times?
A4 “Higher Order” functions to the rescue. A higher order function is a function that takes another function as an input parameter or returns a function. In the following example, it makes the code reusable for different functions like “fibNaive”, “fibTail”, and “fibLoop” by modifying the “test()” function to take a function as an input parameter. “Long => Long” is a function.

Q5 Is there anything else not right with the above Fibonacci code?
A5 #1. The data type “Long” will start to overflow for larger values of “n” like the 95th Fibonacci number. So, favor using a BigInt data type as opposed to a Long.

#2. Use nested functions as shown below.

#3. Use pattern matching instead of if/else.

Note: The variable “zero” is wrapped with a single quote in pattern matching. The @tailrec annotation checks if the annotated function contains a tail recursion, and if it doesn’t, gives a compilation error.

Scala functions like foldLeft, foldRight, scanLeft, scanRight, etc are accumulating functions that make use of recursion.

Answers are detailed to be useful beyond job interviews. A few Q&As each day will make a huge difference in 3 to 24 months to go places depending on your experience.