Tail Recursion

29

Dec

Tail Recursion

My Kid’s encounter with Iteration

I was teaching the addition of 2 numbers to my 5-year-old kid. The initial approach is to use fingers in the hand, so she could sum 2 numbers which add up to a maximum of 10. When it went beyond 10, she needed a placeholder (a variable in software terms). Now I taught her to have one of the numbers in mind so that she could just count the fingers for the second number. Again if the second number is bigger than 10, she was limited. When I started questioning about what her next approach will be, I was surprised by her answer. She came up with an iteration algorithm! The Idea is to use a counter (0n paper) for the number of times the set of 10 fingers were counted. This triggered my thoughts about iteration and recursion, hence this blog post.

 Iteration & Recursion

Recursion had been there in software for very long time. Recursion in software is derived from its mathematical formulations. Below are the rules of recursion.

  1. A simple base case (or cases)
  2. A set of rules that reduce all other cases toward the base case

If we can categorize each of the iteration into a form of simple base cases, then the iterative operation can be made recursive. In simple form: A function calls itself. A ‘Recursion’ is a special form of Iteration where no one knows the number of times the iteration will happen. Below is an example of recursion based Fibonacci series generator.

 
        public int Fibonacci(int n)
        {
            if (n == 0)
                return 0;
            else if (n == 1)
                return 1;
            else
                return (Fibonacci(n - 1) + Fibonacci(n - 2));
        }

 

 Stack Based Languages/Frameworks

Recursive logic in stack based languages/frameworks(example .net, Java)are limited by the amount of memory available. This is because these frameworks add the method name and the data(value types) to a top of the call stack for every call to a method. This is done to retain the data in the current method (in the stack) so that when the method returns, the data can be popped out the stack for usage.The data in the stack is not useful if they are not used after the method call.

 
public void PrintCallStack()
{
  var stackTrace = new StackTrace();           // get call stack
  var stackFrames = stackTrace.GetFrames();  // get method calls (frames) 
  foreach (StackFrame stackFrame in stackFrames)
  {
    Console.WriteLine(stackFrame.GetMethod().Name); 
  }
}

 

 Tail recursion (example)

A recursive method is called Tail recursive if the last line of the method calls itself. Since there are no other operations done after the recursive call, the stack data is useless. So the stack need not be built for each of the recursive calls. A compiler is said to be Tail recursive if it can identify the above scenario and replace the caller with called, and the current stack is reused. This is a huge performance optimization and you might never encounter Stack Overflow exception during recursion.

 
public int NonTailRecursiveFactorial(int n)
{
    if (n < 2)
        return 1;
    return n * Factorial(n - 1);
}
 
public int TailRecursiveFactorial(n, a)
 {
    if (n == 0) return a;
    return TailRecursiveFactorial(n - 1, n * a);
  }


Tail recursion is some times equivalent to Goto statements

public int factorial(int n, int a) 
{ 
beginning: 
if (n == 0) return a; 
else 
  { 
     a *= n; 
     n -= 1; 
     goto beginning; 
   } 
}

 

 By the way..

Generally Tail recursion (tail call optimization) is attributed to functional programming languages and unfortunately major programming languages like C# and Java does not support Tail Recursion. But this optimization is available in their sister frameworks F# and Scala. Also there are thoughts like Trampolines and Lambda expressions are far superior method to achieve results than other form of iterative programming. But i think that is a separate post altogether.

3 thoughts on - Tail Recursion

  • Reply Dec 29, 2014 at 5:31 pm

    Stricly speaking, is your factorial example truly tail recursive? The last operation that is done in the function is a multiplication, not a call to Factorial. At least, that is what the Wikipedia article about “tail call” would appear to say.

    • srkshanky
      Reply Dec 29, 2014 at 5:59 pm

      That’s correct. Factorial method is not tail recursive. Adding the correct method

  • Reply Dec 30, 2014 at 4:43 am

    Good one. I used recursion without even knowing it in a tool that I was writing. And boy is that lovely.

Leave a Reply

Your email address will not be published. Required fields are marked *