What Is Recursion Function In Data Structures ??????
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily..
What is base condition in recursion?
In the recursive program, the solution to the base case is provided and the solution of the bigger problem is expressed in terms of smaller problems.
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
What is the difference between direct and indirect recursion?
A function fun is called direct recursive if it calls the same function fun. A function fun is called indirect recursive if it calls another function say fun_new and fun_new calls fun directly or indirectly. Difference between direct and indirect recursion has been illustrated in Table 1.
// An example of direct recursion
void directRecFun()
{
// Some code....
directRecFun();
// Some code...
}
// An example of indirect recursion
void indirectRecFun1()
{
// Some code...
indirectRecFun2();
// Some code...
}
void indirectRecFun2()
{
// Some code...
indirectRecFun1();
// Some code...
}
Types of recursion .............
Linear Recursive
A linear recursive function is a function that only makes a single call to itself each time the function runs (as opposed to one that would call itself multiple times during its execution). The factorial function is a good example of linear recursion.
Another example of a linear recursive function would be one to compute the square root of a number using Newton's method (assume EPSILON to be a very small number close to 0):
double my_sqrt(double x, double a){ double difference = a*x-x; if (difference < 0.0) difference = -difference; if (difference < EPSILON) return(a); else return(my_sqrt(x,(a+x/a)/2.0));}
Tail recursion is a form of linear recursion. In tail recursion, the recursive call is the last thing the function does. Often, the value of the recursive call is returned. As such, tail recursive functions can often be easily implemented in an iterative manner; by taking out the recursive call and replacing it with a loop, the same effect can generally be achieved. In fact, a good compiler can recognize tail recursion and convert it to iteration in order to optimize the performance of the code.
A good example of a tail recursive function is a function to compute the GCD, or Greatest Common Denominator, of two numbers:
int gcd(int m, int n)
{
int r;
if (m < n) return gcd(n,m);
r = m%n;
if (r == 0) return(n);
else return(gcd(n,r));
}
Some recursive functions don't just have one call to themself, they have two (or more). Functions with two recursive calls are referred to as binary recursive functions.
The mathematical combinations operation is a good example of a function that can quickly be implemented as a binary recursive function. The number of combinations, often represented as nCk where we are choosing n elements out of a set of k elements, can be implemented as follows:
int choose(int n, int k)
{
if (k == 0 || n == k) return(1);
else return(choose(n-1,k) + choose(n-1,k-1));
}
An exponential recursive function is one that, if you were to draw out a representation of all the function calls, would have an exponential number of calls in relation to the size of the data set (exponential meaning if there were n elements, there would be O(an) function calls where a is a positive number).
A good example an exponentially recursive function is a function to compute all the permutations of a data set. Let's write a function to take an array of n integers and print out every permutation of it.
void print_array(int arr[], int n)
{
int i;
for(i=0; i<n; i) printf("%d ", arr[i]);
printf("\n");
}
void print_permutations(int arr[], int n, int i)
{
int j, swap;
print_array(arr, n);
for(j=i+1; j<n; j) {
swap = arr[i]; arr[i] = arr[j]; arr[j] = swap;
print_permutations(arr, n, i+1);
swap = arr[i]; arr[i] = arr[j]; arr[j] = swap;
}
}
To run this function on an array arr of length n, we'd do print_permutations(arr, n, 0) where the 0 tells it to start at the beginning of the Array.
In nested recursion, one of the arguments to the recursive function is the recursive function itself! These functions tend to grow extremely fast. A good example is the classic mathematical function, "Ackermann's function. It grows very quickly (even for small values of x and y, Ackermann(x,y) is extremely large) and it cannot be computed with only definite iteration (a completely defined for() loop for example); it requires indefinite iteration (recursion, for example).
Ackermann's function
int ackerman(int m, int n)
{
if (m == 0) return(n+1);
else if (n == 0) return(ackerman(m-1,1));
else return(ackerman(m-1,ackerman(m,n-1)));
}
Try computing ackerman(4,2) by hand... have fun!
A recursive function doesn't necessarily need to call itself. Some recursive functions work in pairs or even larger groups. For example, function A calls function B which calls function C which in turn calls function A.
A simple example of mutual recursion is a set of function to determine whether an integer is even or odd. How do we know if a number is even? Well, we know 0 is even. And we also know that if a number n is even, then n - 1 must be odd. How do we know if a number is odd? It's not even!
int is_even(unsigned int n)
{
if (n==0) return 1;
else return(is_odd(n-1));
}
int is_odd(unsigned int n)
{
return (!iseven(n));
}
I told you recursion was powerful! Of course, this is just an illustration. The above situation isn't the best example of when we'd want to use recursion instead of iteration or a closed form solution. A more efficient set of function to determine whether an integer is even or odd would be the following:
int iseven(signed int n)
{
if (n % 2 == 0) return 1;
else return 0;
}
int isodd(signed int n)
{
if (n % 2 != 0) return 1;
else return 0;
}
Tail recursive
Binary Recursive
Exponential recursion
Nested Recursion
Mutual Recursion
PRESS BELOW LINK FOR FIND CHARACTERISTICS OF RECURSION
Use of Recursion.........
Recursion is a programming technique that allows the programmer to express operations in terms of themselves. In C, this takes the form of a function that calls itself. A useful way to think of recursive functions is to imagine them as a process being performed where one of the instructions is to "repeat the process". This makes it sound very similar to a loop because it repeats the same code, and in some ways it is similar to looping. On the other hand, recursion makes it easier to express ideas in which the result of the recursive call is necessary to complete the task. Of course, it must be possible for the "process" to sometimes be completed without the recursive call. One simple example is the idea of building a wall that is ten feet high; if I want to build a ten foot high wall, then I will first build a 9 foot high wall, and then add an extra foot of bricks. Conceptually, this is like saying the "build wall" function takes a height and if that height is greater than one, first calls itself to build a lower wall, and then adds one a foot of bricks
Circular queue in C with Example ...................
A circular queue is a very important data structure because it can store data in a very practical way. The circular queue is a linear data structure. It follows FIFO principle. In circular queue, the last node is connected back to the first node to make a circle. Circular array list fallows the First In First Out principle. Elements are added at the rear end and the elements are deleted at the front end of the queue.
# define MAX 5
int cqueue_arr[MAX];
int front = -1;
int rear = -1;
/*Begin of insert*/
void insert(int item)
{
if((front == 0 && rear == MAX-1) || (front == rear+1))
{
printf("Queue Overflow \n");
return;
}
if (front == -1) /*If queue is empty */
{
front = 0;
rear = 0;
}
else
{
if(rear == MAX-1) /*rear is at last position of queue */
rear = 0;
else
rear = rear+1;
}
cqueue_arr[rear] = item ;
}
/*End of insert*/
/*Begin of del*/
void del()
{
if (front == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",cqueue_arr[front]);
if(front == rear) /* queue has only one element */
{
front = -1;
rear=-1;
}
else
{
if(front == MAX-1)
front = 0;
else
front = front+1;
}
}
/*End of del() */
/*Begin of display*/
void display()
{
int front_pos = front,rear_pos = rear;
if(front == -1)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
if( front_pos <= rear_pos )
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
else
{
while(front_pos <= MAX-1)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
}
printf("\n");
}
/*End of display*/
/*Begin of main*/
int main()
{
int choice,item;
do
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
printf("Input the element for insertion in queue : ");
scanf("%d", &item);
insert(item);
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("Wrong choice\n");
}
}while(choice!=4);
return 0;
}
/*End of main*/
 |
| Images by Includehelp.com |
In the Code below there are four parts. First three function to implement three different operations like Insert a node, delete a node and display the list. The Fourth part is the main function, in that a do while loop is implemented to keep the user engaged and provide him the all the given choices, according to the choice one of the three function get called.
The First function checks whether the queue is empty, rear is at last position of queue or Queue is full. If the queue is not full it adds up the item.
The Second function checks whether the list is empty, full or it has only one item. If any node exists, it will delete the node in FIFO order.
The Third function will simply print all the elements of the Queue if exist. If not, then it will say Queue is Empty.
The Queue can hold only 5 items, for changing the capacity edit the second line.
Ok ................
Posts
0 Comments
Write your comments or feedback here.........