Types Of recursion

Detail About Recursion and its Type

Page 1 of 1

2 Replies - 27401 Views - Last Post: 07 May 2008 - 07:47 AM Rate Topic: ***** 1 Votes

#1 asadullah.ansari  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 3
  • View blog
  • Posts: 11
  • Joined: 16-January 08

Types Of recursion

Posted 07 May 2008 - 01:14 AM

Detail About Recursion and its Type

Here I am going to give a detail about Recursion in C++.
Definition: Recursion is the process where a function is called itself but stack frame will be out of limit because function call will be infinite times. So a termination condition is mandatory to a recursion.
In C++, Recursion can be divided into two types:
(a) Run- Time Recursion: Normal as in C
(B) Compile- Time Recursion: By using Template

Each of these can be also divided into following types:

1. Linear Recursion
2. Binary Recursion
3. Tail Recursion
4. Mutual Recursion
5. Nested Recursion


1. Linear Recursion: This recursion is the most commonly used. In this recursion a function call itself in a simple manner and by termination condition it terminates. This process called 'Winding' and when it returns to caller that is called 'Un-Winding'. Termination condition also known as Base condition.

Example: Factorial calculation by linear recursion

Run-Time Version

 int Fact(long n)
{
 	if(0>n)
			   return -1;
	if(0 == n)
	   return 1;
	else
{
	  return ( n* Fact(n-1));
}
}







Winding Process:

Function called Function return

Fact(6) 6*Fact(5)
Fact(5) 5*Fact(4)
Fact(4) 4*Fact(3)
Fact(3) 3* Fact(2)
Fact(2) 2* Fact(1)
Fact(1) 1* Fact(0)
Terminating Point
Fact(0) 1

Unwinding Process

Fact(1) 1*1
Fact(2) 2*1
Fact(3) 3*2*1
Fact(4) 4*3*2*1
Fact(5) 5*4*3*2*1
Fact(6) 6*5*4*3*2*1


Compile-Time Version

// template for Base Condition
template <>
struct Fact<0>
{
   enum 
  { 
	  factVal = 1 
   };
};

template <int n>
struct Fact
{
   // Recursion call by linear method
   enum
  { 
value = n * Fact<n - 1>::factVal
   };
}; 

To test it how it's working at compile time, just call
cout << Fact<-1>::factVal ;
And compile it then compiler error will come, because no template for -1.

2. Binary Recursion: Binary Recursion is a process where function is called twice at a time inplace of once at a time. Mostly it's using in data structure like operations for tree as traversal, finding height, merging, etc.

Example: Fibonacci number

Run Time Version Code:
int FibNum(int n)
{
   // Base conditions
	  if (n < 1)
		 return -1;
	  if (1 == n || 2 == n)
		return 1;

   // Recursive call by Binary Method
	 return FibNum(n - 1) + FibNum(n - 2);   // At a time two recursive function called so			   
																	  //   binary
}


Compile Time Version Code
// Base Conditions
template<>
struct FibNum<2>
{
   enum { val = 1 };
};
template <>
struct FibNum<1>
{
   enum { val = 1 };
};

// Recursive call by Binary Method
template <int n>
struct FibNum
{   
   enum { val= FibNum<n - 1>::val + FibNum<n - 2>::val };
};

3. Tail Recursion: In this method, recursive function is called at the last. So it's more efficient than linear recursion method. Means you can say termination point will come(100%) only you have to put that condition.

Example: Fibonacci number

Run Time Version Code:
int FibNum(int n, int x, int y)
{   
   if (1 == n)	// Base Condition
   {
	  return y;
   }
   else		// Recursive call by Tail method
  {
	  return FibNum(n-1, y, x+y);
   }
}


Compile Time Version Code

template <int n, int x, int y>
struct FibNum
{
   // Recursive call By tail method
   enum 
  { 
		val = FibNum<n-1, y, (x+y)>::val
   };
};

// Base Condition or Termination 
template<int x, int y>
struct FibNum<1, x, y>
{
   enum 
  {
	  val = y 
   };
};





4. Mutual Recursion: Functions calling each other. Let's say FunA calling FunB and FunB calling FunA recursively. This is not actually not recursive but it's doing same as recursive. So you can say Programming languages which are not supporting recursive calls, mutual recursion can be applied there to fulfill the requirement of recursion. Base condition can be applied to any into one or more than one or all functions.

Example: To find Even Or Odd number

Run Time Version Code:
bool IsOddNumber(int n)
{
   // Base or Termination Condition
   if (0 == n)
	  return 0;
   else
	  // Recursive call by Mutual Method
	  return IsEvenNumber(n - 1);
}

bool IsEvenNumber(int n)
{
   // Base or Termination Condition
   if (0 == n)
	  return 1;
   else
	  // Recursive call by Mutual Method
	  return IsOddNumber(n - 1);
}



Compile Time Version Code


// Base Or Termination Conditions
template <>
struct IsOddNumber<0>
{
   enum 
  {
	 val = 0 
  };
};
template <>
struct IsEvenNumber<0>
{
   enum 
  { 
	  val = 1 
  };
};

// Recursive calls by Mutual Method

template <int n>
struct IsOddNumber
{
   enum 
  { 
		 val = n == 0 ? 0 : IsEvenNumber<n - 1>::val 
   };
};


template <int n>
struct IsEvenNumber
{
   enum 
  { 
	   val = n == 0 ? 1 : IsOddNumber<n - 1>::val
  };
};

 


3. Nested Recursion: It's very different than all recursions. All recursion can be converted to iterative (loop) except nested recursion. You can understand this recursion by example of Ackermann function.

Example: Ackermann function

Run Time Version Code:
int Ackermann(int x, int y)
{
	  // Base or Termination Condition
	if (0 == x)
   {
	  return y + 1;
 }   
// Error Handling condition
   if (x < 0  ||  y < 0)
  {
	  return -1;
   }  
// Recursive call by Linear method 
   else if (x > 0 && 0 == y) 
  {
	  return Ackermann(x-1, 1);
  }
   // Recursive call by Nested method
   else
  {
	  return Ackermann(x-1, Ackermann(x, y-1));
  }
}


Compile Time Version Code
// Base Or Termination condition
template <int y>
struct Ackermann<0, y>
{
   enum { val = y + 1 };
};

   // Recursive Call by Linear Method
template <int x>
struct Ackermann<x, 0>
{
   enum 
   { 
			val = Ackermann<x-1, 1>::val
   };
};

// Recursive Call by Nested Method
template <int x, int y>
struct Ackermann
{
   Enum
   { 
		 val = Ackermann<x-1, Ackermann<x, y-1> ::val>::val 
   };
};

Attached File(s)



Is This A Good Question/Topic? 1

Replies To: Types Of recursion

#2 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3116
  • View blog
  • Posts: 19,153
  • Joined: 14-September 07

Re: Types Of recursion

Posted 07 May 2008 - 05:50 AM

If this is supposed to be a tutorial you need to submit it there instead of here.

C++ Tutorial Section
Was This Post Helpful? 0
  • +
  • -

#3 jeronimo0d0a  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 146
  • Joined: 03-March 08

Re: Types Of recursion

Posted 07 May 2008 - 07:47 AM

I don't think that binary recursion really is recursive because the function will return before it is called again. Also, the nested recursion doesn't call itself and if you check the call stack with the debugger, there is no recursion even though it looks like there would be from the code.

This post has been edited by jeronimo0d0a: 07 May 2008 - 07:56 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1