Page 158 - DCAP407_DATA_STRUCTURE

Unit 9: Recursion

In Computer Science and Mathematics, recursion just means self reference. Therefore, a recursive
function is a function whose definition is based upon itself. In other words, a function that contains a
call statement to itself or a call statement to another function that may eventually result in a call back to
the original function is termed as a recursive function.
Recursion defines a problem in terms of itself. A recursive solution repeatedly divides a problem into
smaller sub problems till a solvable sub problem is attained. After obtaining the answer for the solvable
sub problem, the answer is fed back into the larger sub problem to obtain the solution. This process
goes on until we solve the main problem.
Let us now discuss the concept of recursion.
Let ‘P’ be the original problem. P can be redefined into sub problems like P 1, P 2 and so on. Let P n be the
last sub problem. If P n sub problem can be defined without any subdivision, then the solution of P n can
be used to solve P n- 1 sub problem. Further, this solution is fed into P n- 2, … P 1 till the original problem
‘P’ has been solved.

Program to count till the entered number and to display information about the
current recursion level

/* A preprocessor directive */
#include <stdio.h>

/* Declare an integer variable named ‘level’ */
int level;

/* Function declaration of count function that accepts an integer val */
void count (int val)
{
/* Print the count value */
printf (“\n Start counting at level % 2d : val = %2d\n”, ++level, val);
/* Checking if variable ‘val’ is greater than 1 */
if (val>1)

/* A recursive call is made passing the value (val-1) */
count (val-1);

/* Print variable ‘val’ value */
printf (“Display val”, val);

/* Print level and val. Then decrement the value of level */
printf (“Stop counting at level %2d : val = %2d\n”, level--, val);
}
/*Main Program*/
void main ()
{
/* Function count and variable int are declared*/
int val;
void count (int);
printf (“Count till what value?”);

/* Accept an integer value and store it in val */
scanf (“%d”, &val);
/* Initialize level value to zero */
level = 0;
/* Calling count function passing val as the parameter */

LOVELY PROFESSIONAL UNIVERSITY 151