Erlang understand recursion -

i have problems understanding recursion , hoping help. have 2 examples answers can't understand how outcomme calculated.

f1(x, [x | ys]) -> [x] ++ f1(x, ys); f1(x, [y| xs]) -> tl(f1(y, xs)) ++ [x]; f1(x, []) -> [x,x]. 

if run code with: f1(2, [1,1,1,6]). -> [1,6,1,2]

another example: f1(c, [f,b,d,d,a]) -> [b,f,c]

can please explain me how function calculates? :)

another recursion function can't grasp one:

f2([x|xs]) when x > 2 ->   [x|f2(xs)]; f2([x|xs]) ->   [y|ys] = f2(xs),   [y,x+y|ys]; f2([]) -> [1]. 

example: f2([3,1,2]). -> [3,1,2,3]. how that?

thanks in advance :)

these examples make use of erlang's pattern matching.

the first clause of first example match if first element of list same first argument

f1(x, [x | ys]) -> [x] ++ f1(x, ys); 

the second clause match other cases list not empty

f1(x, [y| xs]) -> tl(f1(y, xs)) ++ [x]; 

and last clause matches empty list.

f1(x, []) -> [x,x]. 

when evaluating f1(2, [1,1,1,6]). first iteration matches second clause, setting x=2, y=1, xs=[1,1,6] calling f1(1,[1,1,6]) , returning tail of result 2 appended

the second iteration f1(1,[1,1,6]) matches first clause, setting x=1, ys=[1,6], calling f1(1,[1,6]) , returning result 1 prepended

the third iteration f1(1,[1,6]) matches first clause, setting x=1, ys=[6], calling f1(1,[6]), , returning result 1 prepended

the fourth iteration f1(1,[6]) matches second clause, setting x=1, y=6, xs=[] calling f1(6,[]), dropping first element, , appending 1 result

the final iteration matches third clause, setting x=6 , returning [6,6]

unwinding stack then:

• drop first element [6,6] , append 1 -> returns [6,1] (fourth call)
• prepend 1 -> returns [1,6,1] (third call)
• prepend 1 -> returns [1,1,6,1] (second call)
• append 2 tail -> returns [1,6,1,2] (first call)

for final value of [1,6,1,2]

in second example, first clause used first element. note since proper list ends empty list, pattern match [y|ys] = [1] set y=1 , ys=[]

edit: adding explanation of second example

%% if first item in list greater 2,  %% return new list consisting of first item prepended  %% result of recursively processing rest of list f2([x|xs]) when x > 2 ->   [x|f2(xs)];  %% in other cases list not empty, save off  %% first element, create new list first  %% element first element returned recursive call,  %% , second element sum of element ,  %% first element saved above, rest of recursive  %% result appended f2([x|xs]) ->   [y|ys] = f2(xs),   [y,x+y|ys];  %% return 1 if passed empty list f2([]) -> [1]. 

so following execution:

1a. `f2([3,1,2])` matches first clause, setting `x=3`, `xs=[1,2]`       2a. `f2([1,2])` matches second clause, setting `x=1`, `xs=[2]`             3a. `f2([2])` matches second clause, setting `x=2`, `xs=[]`               4. `f2([])` matches second clause, returning [1]           3b. `[y|ys] = [1]` sets `y=1`, `ys=[]`           3c. returns `[1, 1 + 2 | []]` i.e. `[1,3]`       2b. `[y|ys] = [1,3]` sets `y=1`, `ys=[3]`       2c. returns `[1, 1 + 1 | [3]]` i.e. `[1,2,3]`   1b.  returns `[3|[1,3,2]]` i.e. `[3,1,2,3]`