#tail recursion

Tail Recursion in JAVA 8

A tail-recursive function is just a function whose very the last action is a call to itself. Tail-Call Optimisation(TCO) lets us convert regular recursive calls into tail calls to make recursions practical for large inputs, which was earlier leading to stack overflow error in normal recursion scenario.

With Scala, making a tail recursive function is easy. The Scala compiler detects tail recursion…

Jump Higher With Trampoline

In our earlier blog The Tale of ‘Tail Recursion’, we have talked about tail recursion. And In this blog, we will be talking about limitation of tail recursion and its solution in scala.

Unfortunately JVM doesn’t support tail call optimization, but scala does as we have seen. However, what if we are not doing simple tail recursion like we usually do. What if on the other hand we have a function…

From Recursion to Tail Recursion in Scala #scala #recursion #optimization

Tail recursion is a kind of special recursion where the last call in function, calls another function or itself. It is basically a functional form of a loop and is advantageous while the function does not have to wait for the result of inner functions and does not fill the memory stack. The tail recursion has a fixed stack size and does not lead to a stack overflow. Since most JVM implementations…

Scala does optimize tail recursion at compile time

I just got wowed. Scala does optimize tail recursion at compile time, I didn’t know that.

Say I have following countDown method —

public static void main(String[] args) { countDown(1_000_000_000); } public static void countDown(int n) { if (n == 0) return; System.out.println(n + " ..."); waitASecond(); countDown(n - 1); } private static void waitASecond() { // do some bla bla }

zip/3 & lenient_zip/3 (Tail Recursion)

zip/2 (not tail recursive)

zip([],[]) -> []; zip([X|Xs],[Y|Ys]) -> [{X,Y}|zip(Xs,Ys)].

zip/3 (tail recursion) My solution

zip(X,Y) -> zip(X,Y,[]). zip([],[],Acc) -> Acc; zip([X|Xs],[Y|Ys], Acc) -> zip(Xs, Ys, [{X,Y}|Acc]).

zip/3 (tail recursion) Book's solution

%% tail recursive version of zip/2 tail_zip(X,Y) -> reverse(tail_zip(X,Y,[])). tail_zip([],[],Acc) -> Acc; tail_zip([X|Xs],[Y|Ys], Acc) -> tail_zip(Xs,Ys, [{X,Y}|Acc]).

My problem: I forgot about the reverse()

lenient_zip/2 (not tail recursive)

lenient_zip([],_) -> []; lenient_zip(_,[]) -> []; lenient_zip([X|Xs],[Y|Ys]) -> [{X,Y}|lenient_zip(Xs,Ys)].

lenient_zip/3 (tail recursion) My solution

lenient_zip(X,Y) -> lenient_zip(X,Y,[]). lenient_zip([],_,Acc) -> Acc; lenient_zip(_,[],Acc) -> Acc; lenient_zip([X|Xs],[Y|Ys],Acc) -> lenient_zip(Xs,Ys,[{X,Y}|Acc]).

lenient_zip/3 (tail recursion) Book's solution

%% tail recursive version of lenient-zip/2 tail_lenient_zip(X,Y) -> reverse(tail_lenient_zip(X,Y,[])). tail_lenient_zip([],_,Acc) -> Acc; tail_lenient_zip(_,[],Acc) -> Acc; tail_lenient_zip([X|Xs],[Y|Ys], Acc) -> tail_lenient_zip(Xs,Ys,[{X,Y}|Acc]).

Picture by Sarah Inteman/John Kiehl

More recursive functions

duplicate/2 function

This function takes an integer as its first parameter and then any other term as its second parameter. It will then create a list of as many copies of the term as specified by the integer.

Module name and interface

--module(duplicate) --export([duplicate/2])

Function parameter is going to be something like this

duplicate(X,Term) ->

base case

where Term=0

duplicate(X, _) -> [].

a function that calls itself

duplicate(X, Term) when X > 0 -> [Term | duplicate(X-1,Term)].

duplicate/2

duplicate(0, _) -> []; duplicate(X, Term) when X > 0 -> [Term | duplicate(X-1,Term)].

duplicate/2 (tail recursion)

duplicate(X, Term) -> duplicate(X, Term, []). duplicate(0, _, List) -> List; duplicate(X, Term, List) when X > 0 -> duplicate(X-1, Term, [Term | List]).

reverse/2 function

Reverse a given list.

reverse/2

reverse([]) -> []; reverse([H|T]) -> reverse(T)++[H].

reverse([1,2,3,4]) = [4]++[3]++[2]++[1] ↑ ↵ = [4,3]++[2]++[1] ↑ ↑ ↵ = [4,3,2]++[1] ↑ ↑ ↑ ↵ = [4,3,2,1].

The diagram from the book is confusing. But it took a bit and a hot shower and I understand it. Look at the code.

Remember this isn't tail recursion. It have to expand and it calculate after it reaches the base and start to pop off the stack. The diagram that the book gave is when already branch all the way down. It's showing us the stack popping where it have to slowly append each list item.

reverse([H|T]) -> reverse(T)++[H].

reverse([1,2,3,4]) = reverse([2,3,4])++[1] = reverse([3,4])++[2]++[1] = reverse([4])++[3]++[2]++[1] = [4]++[3]++[2]++[1] = [4,3]++[2]++[1] = [4,3,2]++[1] = [4,3,2,1]

reverse/2 tail recursion

reverse(List) -> reverse(List, Acc) reverse([],Acc) -> Acc; reverse([H|T],Acc) -> reverse(T,[Acc|H]).

tail_reverse([1,2,3,4]) = tail_reverse([2,3,4], [1]) = tail_reverse([3,4], [2,1]) = tail_reverse([4], [3,2,1]) = tail_reverse([], [4,3,2,1]) = [4,3,2,1]

sublist/2 function

...which takes a list L and an integer N, and returns the N first elements of the list.--book

base case

where N=0 and L=[] (an empty list)

duplicate(0, []) -> []; duplicate(_,[]) -> [];

a function that calls itself

duplicate(N,[H | T]) when N > 0 -> [H | duplicate(N-1,T)].

Is this right? Not sure because I don't believe the base case of duplicate(0, []) -> []; would work. I'm thinking it's duplicate(0, L) -> L; Oh well time to check the book solution.

Book's solution

sublist(_,0) -> []; sublist([],_) -> []; sublist([H|T],N) when N > 0 -> [H|sublist(T,N-1)].

Ah, should be sublist(_,0) -> [];. My parameter order is different from the book and I forgot that the function is named sublist not duplicate.

sublist/2 tail recursion

Tail recursion my answer modifying the book non-tail recursion answer:

sublist/2 tail recursion (my answer)

sublist(L, N) -> sublist(L, N, []). sublist(_, 0, Acc) -> Acc; sublist([], _, Acc) -> Acc; sublist([H|T], N, Acc) when N > 0 -> sublist(T, N-1, [H | Acc]).

sublist/2 tail recursion (book's answer)

tail_sublist(L, N) -> tail_sublist(L, N, []). tail_sublist(_, 0, SubList) -> SubList; tail_sublist([], _, SubList) -> SubList; tail_sublist([H|T], N, SubList) when N > 0 -> tail_sublist(T, N-1, [H|SubList]).

A fatal flaw!

If you compile this function as is, sublist([1,2,3,4,5,6],3) would not return [1,2,3], but [3,2,1].

Okay Solution

tail_sublist(L, N) -> reverse(tail_sublist(L, N, [])).

Better Solution

tail_sublist(L, N) -> lists:reverse(tail_sublist(L, N, [])).

zip/2 function

A zipping function will take two lists of same length as parameters and will join them as a list of tuples which all hold two terms.--book

Example of zip/2

1> recursive:zip([a,b,c],[1,2,3]). [{a,1},{b,2},{c,3}]

base case

where L1=[], L2=[]

zip([],[]) -> [];

a function that calls itself

zip([H1 | T1],[H2 | T2]) -> [{H1, H2}, zip(T1, T2)];

Book's solution

zip([],[]) -> []; zip([X|Xs],[Y|Ys]) -> [{X,Y}|zip(Xs,Ys)].

My mistakes: . instead of ; and , instead of |

However, if you wanted a more lenient zip function, you could decide to have it finish whenever one of the two list is done.--book

Book's solution