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#.