Recursion

2 types of recursion exist:

Tail	Non-Tail
void Tail(int i) { if(i > 0) { Console.WriteLine(i); Tail(i-1); } }	void NonTail(int i) { if(i > 0) { NonTail(i-1); Console.WriteLine(i); NonTail(i-1); } }

Tail Recursion

• The simplest case. A glorified loop.
  
• Can simply be replace by iterative method.
  
• The basic idea behind Tail Recursion is to eliminate the storage of any state information across the recursive steps. All information that would ever be needed at any single step is passed as a parameter to the function instead of being stored at some higher level in the recursion stack.
  
• In tail recursion, the recursive call should be the ONLY last statement, and there should be no earlier recursive calls whether direct or indirect.
  
• Used to implement loops in languages that do not support loop structures explicitly (e.g. prolog).

Example convert Tail recursion to iterative:

for loop syntax

for(init; condition; increment)
    statement;

Tail	Iterative
void Tail(int i) { if(i > 0) { Console.WriteLine(i); Tail(i-1); } }	void Tail(int i) { for(; i>0; i--) Console.WriteLine(i); }

Tail Recursion Examples:

public static void f1(int n)
{ 
    Console.WriteLine(n);  
   
    if(n > 0)    
      f1(n - 1); //last statement with recursive call
}

public static void f3(int n)
{
    if(n > 6)
    {
        Console.WriteLine(2*n);
        f3(n – 2); //last statement with recursive call

    } else if(n > 0)
    {
        Console.WriteLine(n);
        f3(n – 1); //last statement with recursive call
   }
}

Non - Tail recursion

Non Tail	Iterative
double Power(double x, int n) { if(n == 0) return 1.0; //condition else return x * Power(x, n-1); }	double Power(double x, int n) { double result = 1.0; //stack for(result = x; n > 1 ; n--) result = result * x; }
string Reverse(string s) { if (s.Length == 1) return s; return Reverse(s.Substring(1)) + s[0].ToString(); }	string Reverse(string s) { string result = string.Empty; for (int i = s.Length - 1; i >= 0; i--) { result = result + s[i].ToString(); } return result; }

Converting Non – Tail Recursion  to Tail Recursion

• A non-tail recursive method can often be converted to a tail-recursive method by means of an "auxiliary" parameter. This parameter (A.K.A Accumulator) is used to form the result.
  
• The idea is to attempt to incorporate the pending operation into the auxiliary parameter in such a way that the recursive call no longer has a pending operation.
  
• The technique is usually used in conjunction with an "auxiliary" method. This is simply to keep the syntax clean and to hide the fact that auxiliary parameters are needed.

Non Tail	Tail
long Factorial (int n) { if (n == 0) return 1; else return n * Factorial (n – 1); }	long Factorial(int n) { return FactAux(n, 1); } long FactAux(int n, int result) { if (n == 0) return result; else return FactAux(n-1, n * result); //using result as accumulator }
int Fib(int n){ if (n == 0 || n == 1) return n; else return Fib(n – 1) + Fib(n – 2); }	int Fib (int n) { return FibAux(n, 1, 0); } int FibAux (int n, int next, int result) { if (n == 0) return result; else return FibAux(n – 1, next + result, next); }

Common errors

• Post increment and decrement operators must not be used since the update will not occur until AFTER the method call - infinite recursion.

public static int SumArray (int[ ] x, int index) 
{
   if (index == x.length)return 0;
   else
      return x[index] + SumArray (x, index++);
} 

• Local variables must not be used to accumulate the result of a recursive method. Each recursive call has its own copy of local variables.

public static int sumArray (int[ ] x, int index)
{
   int sum = 0;
   if (index == x.length)return sum;
   else {   
      sum += x[index];
      return sumArray(x,index + 1);
   }
}

• Wrong placement of return statement.

incorrect version (always return initial pass in result)

public static int Sum(int n, int result) 
{
   if (n >= 0)
      Sum(n - 1, n + result);
   return result;
}

correct version:

public static int Sum(int n, int result)
{ 
   if (n == 0)
      return result;
   else
      return Sum(n-1, n + result);
}