Different kind of recurrsions in erlang

Question

I think it may be the pretty much basic question. What are the different types of recursions that we use in the functional programming. And what kind of recursions that we use the programming language Erlang.

I don't exactly understand the question. Recursion is the same as in other languages. One 'special' thing is optimization of "tail recursive" functions. Do you want to know more about this topic or about general recursion http://en.wikipedia.org/wiki/Recursion_(computer_science)#Types_of_recursion — tkowal, Sep 20 '14 at 10:58

score 1 · Answer 1 · answered Sep 20 '14 at 15:33

1

I'd recommend you to read classics: http://mitpress.mit.edu/sicp/ especially part: 1.2 Procedures and the Processes They Generate

answered Sep 20 '14 at 15:33

user3169252

1,139
1
9
13

This is an extremely good recommendation, and one that will improve the OP's understanding beyond just Erlang. It is common that folks just have to read and re-read that part of SICP until it really makes sense. – zxq9 Sep 30 '14 at 01:54

score 1 · Answer 2 · edited May 23 '17 at 11:57

I would recommend looking into Learn You Some Erlang since it is nice and comprehensive description of this topic.

In short there are two types, distinguished by semantics rather than syntax.

There is basic requisition one can see in almost any other language

fibonacci ( 0 ) -> 
   0;
fibonacci ( 1 ) ->
   1;
fibonacci( X ) when X > 1 ->
   fibonacci( X-1 ) + fiboancci( X-2 ).

And this is working with expected stack memory usage (new stack for almost each function call.

And there is something called tail recursion. When recursive function is last being called, the compiler can skip creating new stack for each call, since there will be no need fir unwinding, returning back to higher level for any other logic. All that is need to done is to return a final value. To understand it better lets look deeper into our example.

In fibonacci above, the last function being called is addition of two numbers. We could rewrite this function to use some kind of counter similar to for loops in other languages, and accumulator, which will be returned at the end (B)

fibonacci(X) ->
    fibonacci( X, 0, 1).

fibonacci( 1, _A, B) ->
    B;
fibonacci( Counter, A, B ) ->
    fibonacci( Counter-1, B, A+B).

This time function fibonacci/3 can be executed without stack unwinding. It's still recursion, with all the same rules and logic, but it is able to be run faster (and without so much memory consumption).

In Erlang this possibility of tail recursion have one important consequance. It allows for long (forever) running processes. If you look at almost any actor with receive clause it fallows similar pattern

loop(SomeState) ->
    receive 
        PatterMatch ->
            [ .. Do some stuff .. ]
            loop(UpdatedState);

        AnotherPatternMatch ->
            [.. different actions ..]
            loop(UpdatedStte);

        stop ->
            ok
    end.

You can easily notice that loop/1 function it recursive. And fact that it is tali recursive allows it to be called time after time without increasing memory usage by this process.

Written with StackEdit.

Different kind of recurrsions in erlang

2 Answers2