Recursion in Erlang

Most computer programming languages support recursion by allowing a function to call itself within the program text. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory has proven[attribution needed] that these recursive-only languages are Turing complete; they are as computationally powerful as Turing complete imperative languages, meaning they can solve the same kinds of problems as imperative languages even without iterative control structures such as “while” and “for”.

A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself). For example, the factorial function can be defined recursively by the equations 0! = 1 and, for all n > 0, n! = n(n − 1)!. Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".

The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. (Functions that are not intended to terminate under normal circumstances—for example, some system and server processes—are an exception to this.) Neglecting to write a base case, or testing for it incorrectly, can cause an infinite loop.

A basic mathematical function such as the factorial of a value is a good example of a function that can be expressed recursively. The factorial of a number n is the product of the sequence 1 x 2 x 3 x ... x n, or alternatively n x (n-1) x (n-2) x ... x 1. To give some examples, the factorial of 3 is 3! = 3 x 2 x 1 = 6. The factorial of 4 would be 4! = 4 x 3 x 2 x 1 = 24. Such a function can be expressed the following way in mathematical notation:

n! = { 1 if n = 0 }, { n((n-1)!) if n > 0 }

What this tells us is that if the value of n we have is 0, we return the result 1. For any value above 0, we return n multiplied by the factorial of n-1, which unfolds until it reaches 1:

4! = 4 x 3!

4! = 4 x 3 x 2!

4! = 4 x 3 x 2 x 1!

4! = 4 x 3 x 2 x 1 x 1

How can such a function be translated from mathematical notation to Erlang? The conversion is simple.

fact(0) -> 1;
fact(N) when N>0 -> N*fact(N-1).
functions:fact(6). //function call


Tail Recursion:-

In traditional recursion, the typical model is that you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. In this manner, you don't get the result of your calculation until you have returned from every recursive call.

In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of "(return (recursive-function params))" .Basically, the return value of any given recursive step is the same as the return value of the next recursive call.

Tail recursion example in erlang-

tail_fact(N) -> tail_fact(N,1).
tail_fact(0,Acc) -> Acc;
tail_fact(N,Acc) when N > 0 -> tail_fact(N-1,N*Acc).
functions:tail_fact(5). //function call


Leave Comment