Scala: Tail recursion
Scala supports functional and imperative styles for programming computing machines. To do repetitive tasks, functional programming exploits recursions while imperative programming exploits control flow loops.
Whenever the data structure that is operated upon is not large like image and video data, functional programming style is considered to be useful for improving code readability and correctness. If Scala were to be the first language for learning functional programming, then there are some pitfalls to guard against because Scala relies on JVM for its execution and JVM was not designed for functional programming. Scala cleverly overcomes the design shortcoming of JVM but Scala's cleverness is not a warrant for programmer's laziness. The programmer must invest time to learn about the theory of functional programming -- returns are high and, so, programmers can choose to make such investment.
An important concept in functional programming is called tail recursion. Lets explore this concept using a simple Scala programming for computing factorial of numbers. The following image shows a Scala code for computing factorial of arbitrary precision numbers using the functional style.
Executing such a code can be perilous as it will result in a runtime error the notorious java.lang.StackOverflowError -- recall that error refers to some bad computation state in the JVM while exception refers to some bad computation state in the application code. Compilers cannot predict errors and testing can only statistically reveal existence of such errors -- that is why the code shown below is called perilous.
The previous code snippet is not tail recursion because the last call in the recursion is to the multiplication function (*). How can it be written as a tail recursion? Basically, the last call by a recursive function must be to itself (factorial).
The code is rewritten as shown here. Notice that the last call by the recursive
function fact is to itself -- i.e. fact. The annotation @tailrec is optional in the above code. Another useful exploration of this concept in Scala (and Clojure) is available in this Q&A posting. Have fun with safe recursions in Scala!
Scala supports functional and imperative styles for programming computing machines. To do repetitive tasks, functional programming exploits recursions while imperative programming exploits control flow loops.
Whenever the data structure that is operated upon is not large like image and video data, functional programming style is considered to be useful for improving code readability and correctness. If Scala were to be the first language for learning functional programming, then there are some pitfalls to guard against because Scala relies on JVM for its execution and JVM was not designed for functional programming. Scala cleverly overcomes the design shortcoming of JVM but Scala's cleverness is not a warrant for programmer's laziness. The programmer must invest time to learn about the theory of functional programming -- returns are high and, so, programmers can choose to make such investment.
An important concept in functional programming is called tail recursion. Lets explore this concept using a simple Scala programming for computing factorial of numbers. The following image shows a Scala code for computing factorial of arbitrary precision numbers using the functional style.
 |
| Factorial computation in Scala without tail recursion |
The previous code snippet is not tail recursion because the last call in the recursion is to the multiplication function (*). How can it be written as a tail recursion? Basically, the last call by a recursive function must be to itself (factorial).
 |
| Factorial code in Scala with tail recursion |
