To understand recursion, you must understand recursion

Recursion is an integral part of functional programming. The emphasis on recursive methods in functional programming is mainly due to the reason that you don't need a mutable state, hence making it simple and straightforward to semantically define a term. Due to this prevalence of recursion as a functional construct and its semantic differences from other functional programming languages like Haskell, F# provides a keyword for recursion that is, rec. This is how you define a recursive function:

let rec recursive-function-identifier parameter-list = 
  recursive-function-body

Factorial is usually a simple example to begin explaining how recursion works. To jog your memory, the factorial of n is the product of all the numbers from , that is,

Hence the output will be as follows:

Since F# is a multi-paradigm language, let's first try to solve this using an imperative approach as seen in the next screenshot:

The iterative implementation of a factorial looks like follows:

let factorialIterative x = 
  let mutable n = x
  let mutable returnVal = 1
  while n >= 1 do
    returnVal <- returnVal * n
    n <- (n - 1)
  returnVal

Tip

Downloading the example code

You can download the example code files for all Packt books you have purchased from your account at http://www.packtpub.com. If you purchased this book elsewhere, you can visit http://www.packtpub.com/support and register to have the files e-mailed directly to you. The GitHub repository for the code files are also available at https://github.com/adnanmasood/Learning-fsharp.

In the preceding code snippet, you will see a few new keywords. It is important to understand that this is non-idiomatic F#; here we are using the mutable keyword, which signifies that the value can be changed. Mutability of a variable is a contentious topic between the purist and pragmatic factions of functional programming. F# allows mutability but also recommends that the scope of mutable variables is kept to a minimum. In the following line of code, if you do not use mutable, the assignment will fail:

n <- (n - 1)

You also see the while loop here. Following is a basic while syntax:

while test-expression do
  body-expression

In this iterative example which is very similar to other procedural language implementations, the while loop runs through n, decreasing value, multiplying, and accumulating the values in the returnVal variable, eventually returning it back. You will also notice that the scope (where the function begins and ends) is maintained through indentation, as compared to C style brackets.

The iterative example just shown is to demonstrate the multi-paradigm nature and flexibility of F#. Now let's do this the right way.

The simple recursive implementation of a factorial invokes itself (recursively), with a decrement in value of n until it reaches 1.

//Recursive
let rec factorial n =
  if n < 1 then 1
  else n * factorial  (n - 1)

Here you notice the use of rec, the F# recursion keyword, and the recursive calling of the factorial method. As shown in the F# interactive window in the following screenshot, when the method is invoked, it displays the factorial of the number:

In this simple recursive factorial method, you can see the elegance and simplicity that distinguishes itself from the iterative implementation. However, recursion is not without dangers for large implementations, such as severe performance penalties and stack overflow, and you need to be careful how, when, and where you decide to implement it. This is probably not a concern when developing and trying out new algorithms. First make it work, and then make it fast. Knuth famously said that premature optimization is the root of all evil in programming.

Tip

Tail recursion is a good way to minimize stack consumption, and increase speed, as will be seen in the examples shortly.

In many F# examples, you will see the pattern matching syntax being used. If you are just starting out with F#, I would recommend against using it because it may end up confusing you. As it is famously said about Perl, that is it is the only language that looks the same before and after RSA encryption, F# syntax matching expressions may end up having the same effect. For instance, the method above can also be written as a pattern matching expression which returns the following equations:

The _ operator is the wildcard expression that matches anything and typically comes last as an everything-else clause. The pipe operator is used to match expressions, and to delimit the matching cases.

The following code snippet is a complete listing for the pattern matching idiomatic F# recursive factorial function:

let rec factorial_PatternMatching n =
  match n with
  | 0 | 1 -> 1
  | _ -> n * factorial(n-1)

Even though the syntax is terse and mathematically sound, this may hinder readability at times. Pragmatically, it is a good idea to use the best judgement in terms of readability, when using the pattern matching statements.

Tail recursion is the optimization applied when the last statement of a function is the recursive call. This eliminates the need for storing the last instruction pointer reference to identify where a function should go to continue execution.

//Tail Recursive 
let factorial n =    
  let rec tailRecFact n accum =
    if n <= 1 then 
      accum
    else 
      tailRecFact (n - 1) (accum * n)
  tailRecFact n 1

By introducing an accumulator variable, we can now accumulate the results and iterate indefinitely, without taking up stack space. The CLR implementation of this method is essentially identical to an iterative while loop.

Another approach to implementing a factorial in functional style is to use continuation. Continuation is a functional programing construct; it is essentially a function that is passed to a function to instruct what needs to be done next.

// Continutaion based factorial
let factorial n =
  let rec contTailRecFact n f =
    if n <= 1 then
      f()
    else
      contTailRecFact (n - 1) (fun () -> n * f())
  contTailRecFact n (fun () -> 1)

Similar to the first implementation with the accumulator, in the preceding code you see the contTailRecFact method. However, now pass a function instead of passing the accumulator variable.

Higher order functions are another construct used to address the concerns raised due to recursive logic. A more idiomatic list-processing approach is using the List.fold <'T, 'State> function. It applies the function to each element of the collection. Several List module functions apply a function to elements. In the case of fold, this is done by threading an accumulator argument (state) through the computation. A generic signature of List.Fold follows:

List.fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State

Simplify the implementation to the following:

let factorial n = [1..n] 
  |> List.fold (*) 1

The same approach can be applied in the case of the List.Reduce method, which chains the results into the next arguments. It takes two parameters—the function used to reduce two list elements to a single element and the list itself. The reduce signature follows:

List.reduce : ('T -> 'T -> 'T) -> 'T list -> 'T

let factorial n = [1..n] 
  |> List.reduce (*)

The List.Reduce method applies the supplied function to each element of the List, threading an accumulator argument. The function is applied to the first two elements of the list, which then passes the result to the function, along with the third element. This continues until the final result is computed.

We realize that this is essentially a whirlwind tour of several important functional programming concepts such as continuations, folding/unfolding, tail call optimization and so on. However, the scope of this book limits us from delving into further details. For curious minds, we have provided details to pertinent resources in Chapter 10, Where to Go Next?.