Application Development, Product to Market
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use

Tail Recursion Example

1/17/2014

0 Comments

 
Picture
Tail recursive saves stack memory.

A recursive function is said to be tail-recursive if there is nothing to do after the function returns except returning its value. In this case, instead of allocating a stack frame for each call, the compiler can rework the code to simply reuse the current stack frame, meaning a tail-recursive function will only use a single stack frame as opposed to hundreds or even thousands of stack frame as in the case of regular recursive calls.

Also, in a tail-recursive case, with each evaluation of the recursive call, the solution (e.g., a running total) is updated through parameter. A smart compiler can make Tail Recursion as efficient as iteration normally is.

We'll see an tail-recursion implementation of Fibonacci at the end of this post. Using Fibonacci as an example, a Fibonacci sequence: [f(0)...f(n)]=[0, 1, 1, 2, 3, 5, 8, 13, ...]

A regular recursive implementation of Fibonacci:
public double fib(int n)  {
  if(n == 0)
    return 0d;
  else if(n == 1)
    return 1d;
  else
    return fib(n - 1) + fib(n - 2);
}
The run-time breakdown of the above intuit but inefficient recursive algorithm which takes a lot of stack space:
  fib(100) 
= fib(99) + fib(98)
= fib(98) + fib(97) + fib(97) + fib(96)
= fib(97) + fib(96) + fib(96) + fib(95) + fib(96) + fib(95) + fib(95) + fib(94)
= ...

You may notice the above  algorithm will be terribly performed with O(2^n). For performance's sake, here's the non-recursive version using a loop:
double f(int n){
    double prev_prev=0d, prev=1d, result=0d;
    for (int i = 1; i <n; i++) {
        result=prev_prev+prev;
        prev_prev=prev;
        prev=result;
    }
    return result;
}
With the above non-recursive code, to get fib(n), simply call f(n-1).

Can't we stay with the recursive way of implementation? Sure. I view tail recursion as a way of introducing a running total which is updated through parameter of the recursive calls. In the Fabonacci example below, 'running tatal' is updated and maintained through 'val' parameter, and the previous value to be calculated toward Fabonocci is passed through the 'prev' parameter:
double fib(int term, double val = 1d, double prev = 0d)
Consider the following tail recursion way of implementation using Groovy's default parameter (not supported by Java):
double fib(int term, double val = 1d, double prev = 0d){
   if(term == 0) return prev;
   if(term == 1) return val;
   return fib(term - 1, val+prev, val);
}

references

  • What is tail-recursion?
  • Bad Code Leads to Bad Conclusions
  • Tail Recursion
0 Comments



Leave a Reply.

    Categories

    All
    Algorithm
    Concurrency
    CQ
    Data Structure
    Design Pattern
    Developer Tool
    Dynamic Programming
    Entrepreneur
    Functional Programming
    IDE
    Java
    JMX
    Marketing
    Marklogic
    Memory
    OSGI
    Performance
    Product
    Product Management
    Security
    Services
    Sling
    Social Media Programming
    Software Development

    Feed Widget

    Archives

    May 2020
    March 2020
    April 2018
    March 2018
    February 2018
    December 2017
    March 2017
    November 2016
    June 2016
    May 2016
    April 2016
    October 2015
    September 2015
    August 2015
    September 2014
    July 2014
    June 2014
    May 2014
    March 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    August 2013
    July 2013
    June 2013

    RSS Feed

in loving memory of my mother  and my 4th aunt
Photos used under Creative Commons from net_efekt, schani, visnup, Dan Zen, gadl, bobbigmac, Susana López-Urrutia, jwalsh, Philippe Put, michael pollak, oskay, Creative Tools, Violentz, Kyknoord, mobilyazilar