Page 169 - DCAP407_DATA_STRUCTURE

Data Structure

Let us see how recursion is implemented.
When a function is invoked, the run-time system allocates memory spaces dynamically for storing
parameters, variables, and constants that are defined within the function. Every function stores a return
address.

Program to illustrate the usage of stack

/* Recursive Call */
/* A preprocessor directive that contains standard input and output operations */
# include <stdio.h>
/* Main function */
main ()
{
/* Initialize x as an integer variable with static as its storage class and assign
0 to it. Static storage refers to the memory locations which persist
Throughout the lifetime of the program. */
static int x = 0;
/* Increment the value of x */
x++;
/* Condition statement: If x is less than 7, the main function itself is
invoked otherwise x value is incremented */
x < 7 ? main () : x++;
/* Print the value of x */
printf (“%2d”, x);
}
Output:
8 8 8 8 8 8 8
In this example:
1. First the stdio.h header file is included using the include keyword.
2. Then, the main function is defined.
3. In main():
(a) First, x is initialized as an integer variable with static as its storage class
and 0 is assigned to it.
(b) Then, x is incremented.
(c) Then, using an ‘if’ condition, the value of x is checked. If x is less than
7, the main function itself is invoked. Otherwise, the value of x is
incremented.
(d) Finally, the value of x is printed.

9.3.1 Factorial of a Number
Calculation of factorial of a number is another program that can be written recursively. Let us discuss
how to write a program to determine the factorial of a number. Factorial of a number ‘n’ can be
determined using the series: 1*2*3*…n = n!
The recursive definition to determine factorial of n is given below:

 ; 1 if n = 0 
Fact ) n ( =  
 n ∗ fact ( − 1n ) otherwise; 

162 LOVELY PROFESSIONAL UNIVERSITY