# [erlang-questions] Modeling Recursion into Tail Recursion

Harit Himanshu <>
Sat Mar 14 15:57:22 CET 2015

```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() ->
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() ->
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.html>
```