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.

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.