Simple Concepts of Functional Programming and Tail Recursion PDF

# 9.4 Simple concepts of functional programming ## 9.4.1 Matching In functional programming we will not use any loops. Instead we work only with recursion. Nevertheless, we need more concepts to write functional code. The branches were one example. But we can make it more clear by using the *match...

# 9.4 Simple concepts of functional programming ## 9.4.1 Matching In functional programming we will not use any loops. Instead we work only with recursion. Nevertheless, we need more concepts to write functional code. The branches were one example. But we can make it more clear by using the *match*-operator. It works similar to the usual branches, but the syntax is easier to read. The idea is to look at an unknown expression and match it with one of several given expressions. Depending on the chosen expression we evaluate differently. Example: ```scala def message(day: String): String = day match case "Monday" => "Start of the week" case "Friday" => "Almost done" case "Saturday" => "Weekend" case "Sunday" => "End of the weekend" case _ => "Work" ``` The symbol `_` is comparable with the *else*-case: every expression will match this so called wild card. We can also put variables here to use the information for further computations: # 9.4.2 Guards Let us consider the following recursive implementation that uses pattern matching: ```scala def fib(n: Int) Int = n match case 0 => 0 case 1 => 1 case _ => fib(n-1) + fib(n-2) ``` We also want to take into account, that an integer might be negative. We can introduce guards to refine the pattern matching. This might look as follows: ```scala def fib_guards (n: Int): Int = n match case 0 => 0 case 1 => 1 case x if x > 1 => fib(x-1) + fib(x-2) case x if x < 0 => throw Exception() // Error handling ``` # 9.5 Tailrecursion If we take a closer look at the implementation of the fibonacci function described then we might see that its running time is quite large³. This comes from the fact that many recursive calls (especially the ones with small parameter) are computed too often. For many recursive functions we can use a technique called accumulator technique. In this technique we remember already computed values and pass them to the recursive call. The recursive call can then immediately compute the final result instead of passing it back to the caller. In fact, we say a function is tail recursive if the last call of the function is the recursive call. ## 9.5.1 Factorial Let us look at an example. The following implementation of *n!* does not use the accumulator technique: ```scala def fac(n: Int) Int = n match case 0 => 1 case _ => n * fac(n-1) ``` This implementation is not tail recursive, since in the second case the last call is not the recursive call but the call of the multiplication. We can use the accumulator technique to make the function tail recursive. Here, we need a help function. ```scala def fac(n: Int) Int = def step(acc: Int, n: Int): Int = n match case 0 => acc case _ => step(n*acc, n-1) step(1, n) ``` As we can see, the function is now tail recursive, since the last call is always the call of the recursion. The parameter *acc* serves as accumulator: it stores intermediate results and passes it to the called function. In the recursion anchor we simply return the accumulator. ## 9.5.3 Why tail recursion Tail recursive functions have several advantages. First of all, we have seen that the running time might decrease, e.g., the running time of fibonacci decreased from *O(φ^n)* to *O(n)*. This comes from the fact that the same expressions are note evaluated for several times. Moreover, the result of the recursive call is not needed to evaluate another expression (there is no back-tracking of the recursive calls). Additionally, the programming language Scala is able to detect whether a function is tail recursive or not. If a function is tail recursive then Scala translates this into an imperative program using a loop. Hence, we can combine two advantages. On the one hand, recursive functions are more readable to humans, and on the other hand, the translation to a loop means that we only need constantly many space. We remember: a recursive function always needs space proportional to the recursion depth. The execution of the following examples can show that Scala optimizes the recursion. ```scala def boom_nontail(n: Int) : Int = if (n == 0) then throw Exception("Boom") else n + boom_nontail(n-1) def boom_tail (n: Int) : Int = if (n == 0) then throw Exception("Boom") else boom_tail(n-1) ``` The first function is not tail recursive. Its invocation `boom_nontail(10)` will show 10 invocations on the stack. The second function is tail recursive. Its invocation `boom_tail(10)` will show only one invocation on the stack - because it was first translated into a loop.