DarkMatter in Cyberspace
  • Home
  • Categories
  • Tags
  • Archives

On Tail Recursion


The essential advantage of tail recursion comparing with ordinary recursion is the efficiency. Why time & space cost of tail recursion is linear while ordinary recursion is more? Chapter 5 of "Learn You Some Erlang for Great Good" by Fred Hebert gives a very concise and intuitive answer: tail recursion is "alone". Following is an example of factorial algorithms to show the difference between these two.

Ordinary Recursion:

fac(N) when N > 0 -> N * fac(N-1).

Tail Recursion:

tail_fac(N, Acc) when N > 0 -> tail_fac(N-1, N*Acc).

So you see, ordinary recursion is "func(state N) -> do something transformation of func(state N-1)", while tail recursion is "func(state N) -> func(state N-1)". This is exact meaning of "alone" above.



Published

May 23, 2013

Last Updated

May 23, 2013

Category

Tech

Tags

  • erlang 15
  • recursion 1

Contact

  • Powered by Pelican. Theme: Elegant by Talha Mansoor