Recursion

RECURSION

 

INTRODUCTION

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.

Example: 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.

Recursion is the process of calling the same function itself again and again until some condition is satisfied. This process is used for repetitive computation in which each action is satisfied in terms of a previous result.

In order to write a recursive program, the user must satisfy the following.

• The problem must be analysed and written in recursive form.

• The problem must have the stopping condition.

Syntax:

function1()

{

       function1();

}

In the above function the function1() is called themselves continuously, so the above function is in recursive manner.

There are certain problems, that can be defined in terms of smaller problems of similar types. Such problems are said to be recursive.

Example: Calculating the factorial of an integer number.

Normally n! = 1×2×3×...Xn (where 'n' is an integer). We can also express this by n!=n*(n‒1)!

This is a recursive statement of the program, in which the desired action is expressed in terms of previous results i.e., value of (n‒1)! Since 1! =1 is the last expression, that provides the stopping condition.

 n! for any non negative value of 'n' is defined as

Here, 'n' recursively defined in terms of itself, hence 5! is calculated as follows:

5! = 5*(5‒1)! = 5*4!

4! = 4*(4‒1)! = 4*3!

3! = 3*(3‒1)! = 3*2!

2! = 2*(2‒1)! = 2*1!

1! = 1*(1‒1)! = 1*1!

Example 1: Program to calculate the factorial of an integer number.

/* Program to calculate the factorial of an integer number */

#include <stdio.h>

main()

{

int a; /*Local definition */

* Statements /

printf("Enter the number:");

scanf("%d",&a);

printf("The factorial of %d=%d", a, rec(a));

} /* main */

rec(int x)    /* rec() is a function it returns the value to main */

int f;

{

/* Statements */

if(x==1)

     return(1);

else

     f=x*rec(x‒1);

return(f);

} /* rec() */

OUTPUT

Enter the number 5

The factorial of 5=120

EXPLANATION: In the above program the variable a is read through the keyboard. The user defined function. rec() is called from the main function. Here the condition checked x=1, if condition is satisfied, then control transfers to the main program and prints the value. Otherwise else part is executed and calculated the factorial value then it returns the value to the main program. The function rec() is referred as a recursion function.

Example 2: Program to read characters and print reversely using recursion.

/* Program to read characters and print reversely using recursion */

#include <stdio.h>

main()

{

void reverse();

printf("Enter Line of Text . . .In");

reverse();

} /* main */

void reverse()

{

char c;

if ((c=getchar())!= '\n') emitido

reverse(); /* The function reverse() is a recursion function */

putchar(c);

} /* reverse() */

OUTPUT

Enter Line of Text . . .munilak

kalinum

EXPLANATION: The main program displays the prompt and then calls the reverse() function. Then the recursive reverse() function reads a single character until end of line (n) is encountered. Each function call reads a new character and pushed it into the stack. Once the end‒of‒line is encountered, then the successive characters are popped from the stack and displayed on a last‒in‒first‒out basis, thus the characters are displayed in reverse order.

Example 3: Program to demonstrate concept of recursion.

/* Program to demonstrate concept of recursion */

#include <stdio.h>

#include <conio.h>

int add(int pk,int pm);

void main()

{

/* Local definitions */

int k,i,m;

m=20;

k=70;

/* Statements */

clrscr();

i=add(k,m); /* call function */

printf("The value of addition is %d\n",i);

getch();

} /* main */

int add(int pk, int pm)

{                               

if(pm==0) return (pk);

     else return(1+add(pk,pm‒1));

} /* add */

OUTPUT

The value of addition is 90

EXPLANATION: In the program m is assigned 20 and k is assigned 70. The main function calls the sub‒program add(). The subprogram add() executes its body and called itself. Then performs the operation and prints the output.

 

TOWER OF HANOI

The Tower of Hanoi is a children's playing game, played with three poles and a number of different sized disks, each disk has a hole in center, allowing it to be stacked around any of the poles. Initially the disks are stacked on the left most pole in the order of decreasing size, i.e., the largest on the bottom and the smallest on the top, as shown in figure given below.

The objective of this game is to transfer the disks from the left most pole to the right most poles, without ever placing a larger disk on the top of the smaller disk. Only one disk may be moved at a time and each disk must always be placed around one of the poles.

The general strategy of the Tower of Hanoi is to consider one of the poles to be the origin, and the other to be the destination, the third pole will be used for intermediate storage, this allows the disks to be moved without placing a larger disk over the smaller one.

Assume that there are 'n' disks numbered from smallest to largest as shown in the figure. If the disks are initially stacked on the left pole, the problem of moving all 'n' disks to the right pole can be stated in the following recursive manner.

i) Move the top n‒1 disks from the left pole to the center pole.

ii) Move the nth disk (largest) to the right pole.

iii) Move the n‒1 disks on the center pole to the right pole.

This can be solved using the above manner for any value of 'n' greater then 0 (If n=0 represents stopping condition)

Example: Program to demonstrate tower of Hanoi.

/* Program using tower of Hanoi */

#include <stdio.h>

main()

{

void hanoi (int, char, char, char); /* Local definition */

/* Statements */

int n;

printf ("How many disk... \n");

scanf("%d", &n);

hanoi (n, 'L', 'R', 'C');

} /* main */

void hanoi (int n, char from, char to, char t)

{

          if (n>0)

          {

                    hanoi (n‒1, from, temp, to);

                    printf ("Move disk %d from %c to %c\n", n, from, to);

                    hanoi (n‒1, temp, to, from);

          } /* if */

} /* hanoi */

OUTPUT

How many disk….. 3

Move disk 1 from L to R

Move disk 2 from L to C

Move disk 1 from R to C

Move disk 3 from L to R

Move disk 1 from C to L

Move disk 2 from C to R

Move disk 1 from L to R

EXPLANATION: In the above program the number of disk n is read and call the subprogram hanoi() from the main function. The function hanoi() checks the condition if (n>0) condition is true then the block of statements are executed and print the poles and sides of the disk. In the program the function hanoi() is referred as a recursion. Where L, R, C are the labels of the poles, i.e., left (L), center (C) and Right (R) and L(From), R(To) and C(t) are the their sources and destination.

Example: Program Binary Search using recursive function.

#include <stdio.h>

#include <stdlib.h>

#define size 10

int binsearch (int[], int, int, int);

int main()

{

int num, i, key, position;

int low, high, list[size];

printf("\nEnter the total number of elements: ");

scanf("%d", &num);

printf("\nEnter the elements of list :");

for(i=0; i < num; i++)

{

scanf("%d", &list[i]);

}

low = 0;

high = num‒1;

printf("\nEnter element to be searched: ");

scanf("%d", &key);

position = binsearch(list, key, low, high);

if (position != ‒1)

          printf("\nNumber present at %d", (position + 1));

else

          printf("\n The number is not present in the list");

return (0);

/*Binary Search function */

int binsearch(int a[], int x, int low, int high)

{

int mid;

if (low > high)

          return ‒1;

mid = (low + high) / 2;

if (x == a[mid])

          return (mid);

else if (x < a[mid])

          binsearch(a, x, low, mid ‒ 1);

else

          binsearch(a, x, mid + 1, high);

OUTPUT

Enter the total number of elements: 5

Enter the elements of list : 3 5 2 6 7

Enter element to be searched :2

Number present at: 3

Enter the total number of elements 5

Enter the elements of list : 6 4 3 2 8

Enter element to be searched : 9

The number is not present in the list