[erlang-questions] Modeling Recursion into Tail Recursion

[Harit Himanshu]

Hello

I was trying to work through finding fibonacci number 10 days ago and my
first attempt looked like

-module(solution).
-export([main/0, fib/2]).


main() ->
  {ok, [N]} = io:fread("", "~d"),
  io:format("~p~n", [fib(N, maps:new())]).

fib(1, _) -> 0;
fib(2, _) -> 1;
fib(N, Map) ->
  case maps:find(N, Map) of
    {ok, Value} -> Value;
    error -> fib(N -1, Map) + fib(N-2, Map)
  end.

Then I realized that tho is going to be very inefficient to store all
values. Plus for large numbers the recursion will create lot more stacks.
no no!

This morning I spent some time to learn the concept of Tail Recursion and
re-tried the same problem again with following code

-module(solution).
-export([main/0]).

main() ->
  {ok, [N]} = io:fread("", "~d"),
  io:format("~p~n", [fib(N, 0, 1)]).

fib(1, Prev, _) -> Prev;
fib(N, Prev, Next) when N > 0 ->
  fib(N-1, Next, Prev + Next).

I wanted to check through the community to learn about better ways to solve
the problem.

*Question*

   1. Since the concept for tail recursion is new to me I specially wanted
   to ask that how could I model my thinking to turn recursive functions into
   tail-recursive functions?
   2. Can we turn every recursive function into tail-recursive? If no, how
   to identify?
   3. Any other valuable recommendation based on your learnings?

Thank you
+ Harit Himanshu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20150314/6c970b15/attachment.htm>