Picture of Travis Hoyt
tail recursion question
by Travis Hoyt - Thursday, 5 January 2012, 12:25 PM
Below is my attempt at the Effects assignment. Everything passed but the Wrangler which said I was not using tail recursion. I guess I'm still having an issue with that concept. How could my code below be changed to leverage tail recursion?


print(0) -> io:fwrite("~n");
print(N) when N > 0 -> print(N-1), io:fwrite("~w ",[N]).

even_print(0) -> io:fwrite("~n");
even_print(N) when N > 0, N rem 2 == 1 -> even_print(N-1);
even_print(N) when N > 0, N rem 2 == 0 -> even_print(N-1), io:fwrite("~w ", [N]).
Picture of Roberto Aloi
Re: tail recursion question
by Roberto Aloi - Wednesday, 18 January 2012, 12:40 PM
Hi Travis,

a "tail-recursive" function is a special case of a "recursive" function, where the last operation performed by the function (tail call) is a call to itself. The usual advantage of a tail-recursive function is that you can use recursion but keep the size of the stack constant (as opposed to a stack growing at each recursive call).

The usual trick to re-write a recursive function into its tail-recursive equivalent is to add an extra parameter to the function, called "accumulator", which contains the partial result accumulated "so-far". In this exercise you could do something like:

print(N) ->
  print(N, 1).

Where you offer to the user the usual print/1 API but then, behind the scenes, you call a second version of the function with an extra parameter. In this case I'm initializing the accumulator to "1". In the print/2 you can then print out the value of the accumulator and then recursive call yourself.

Please note that I'm not suggesting this as a solution to the exercise. Your solution is perfectly fine. In fact, Wrangler's message is simply a "warning", to make you reflect about this aspect. Not always tail-recursive functions are better than standard recursive functions. Here's an explanation about why Tail Recursion in Erlang is not always a silver bullet.