Understanding Recursion in F#

Introduction

The first functional concept that you need to become familiar with is that of Recursion. In mathematics, and in programming a Recursive Function is one in Which the function being defined is applied with in its own definition. Recursion is the most celebrated way of avoiding iteration in functional Programming is to use its more sophisticated alternative. Simply you can say Recursion means defining a Function in terms of itself. In other words the function calls itself within its definitions. Loops are used in Imperative programming where as Recursion is often used with Functional programming. F# treats Recursive function just as a bit differently than regular functions. If you want to make a Function act Recursive you just need to use the keyword rec.

Functions in F# are not recursive by default. A programmers needs to explicitly make a function as Recursive by using rec keyword. rec keyword does not change the Functions fundamental type. Recursive Function call themselves by pushing the current state of the function on to the stack and popping them off when calls start completing, because the stack is a limited resource. It is often useful to think of recursion in terms of base case and the recursive case. The recursive case is the value for which the function is defined in terms of itself, where as the base case is the nonrecursive case: that is there should be some value where the function is not defined in terms of itself.

Example 1

// sum of first 5 integers using recursion
let rec sumN x =
        if x = 0 then 0 else x + sumN(x-1)
printfn "The sum of first 5 itegers is- %A" (sumN 5)

Here we are discussing a very simple example of recursion to sum the N integer numbers recursively. The first thing to note it that SumN(0) has to be zero and if the parameter is any other value other than zero then sumN(x)=x+sumN(x-1). In this example first sumN(5) will called which starts to evaluates 5+sumN 4 but will wait until sumN 4 has finished computing the sum of the first five integers and sumN4 will wait till sumN 3 evaluates and so on.

Output

Example 2

Now we are discussing one example of factorial using Recursion.

// factorial of a number using recursion
open System
let rec factorial x =
    if x <= 1 then 1 
    else x * factorial(x-1)
let result= factorial 6
Console.WriteLine(factorial 6)

Output

The few points to remember regarding using recursion.

• Call itself recursively.
• Change its state and move towards the base case.
• Have a base case.

Tail Recursion

Tail Recursion is essential feature in Functional languages like F#. Where iterative solutions are often implemented using Recursion. Tail recursion is the process of recursively calling a methods that eats through the list and processing one element at a time. A Tail Recursive function is a special case of recursion in which the last instruction executed in the method is the recursive call. Such recursion can be easily transformed to iterations. F# optimizes Tail recursive function by telling the CLR to drop the current stack frame before executing the target function and the result is that Tail recursive function can call itself indefinitely without consuming stack space. Tail Recursion simply called the best form of the recursion because it does not leave a waiting trail of part completed expressions on the stack. In Tail recursion function ends with a simple call to itself.

Example

Now we are discussing the above example of sum of n integers in Tail recursion form.

// sum of n itegers using Tail recursion
let rec sumN x acc=
        if x = 0 then acc
        else  sumN (x-1)(x+acc)
//let sumn x=sumN x 0
printfn "The sum of first 5 itegers is- %A" (sumN 5 0) //currying

Output

Currying

In Tail recursion we are initializing acc; that is accumulator, so there will be a slight change in calling convention. when we find the some of n integers we will use

printfn "The sum of first 5 itegers is- %A" (sumN 5 0)

In this the accumulator always set to zero we will create a new function from sumN with the second parameter set to zero like above. This is called "currying".

if we use the below syntax.

let rec sumN x acc=
        if x = 0 then acc
        else sumN (x-1) (x+acc)
let sumn x=sumN x 0
printfn "The sum of first 5 itegers is- %A" (sumN 5 )

Now there is no need to specify zero with above syntax.

Mutual Recursion

An important concept of functional programming in F# is another type of recursion; that is Mutual Recursion. Mutual Recursion is useful when two function needs to call each other and functions are called Mutually recursive.

Example

// fibonacci series using Mutual recursion
let rec f(x)= if x=1 then 1 else g(x-1)
and g(x)= if x=1 then 0 else g(x-1)+f(x-1)
let mutrec_fibonacci(x)=f(x)+g(x)
let mutrec_d=mutrec_fibonacci(9)
printfn "%d" mutrec_d

Output

Anonymous Recursion

A recursive function that we should resort to a separate helper function to handle the actual recursion. This is the case when directly calling the current function would waste many resource cause unwanted side effects and the function does not have the right argument and return values. The purpose of Anonymous recursion is to avoid to create helper functions that are only intended to be used inside another function but still look like a part of module. You can also accomplish Anonymous recursion using Y Combinator.

Example

//Fibonacci series using Anonymous recursion
let fibo = function
    | x when x < 0 -> None
    | x -> let rec fibo2 = function
               | 0 | 1 -> 1
               | x -> fibo2 (x-1) + fibo2 (x-2)
            in Some (fibo2 x)
printfn "the fibo series's %A" (fibo 7)

Output

Summary

In this article I have covered Recursion and its Types in F#.