Page 160 - DCAP407_DATA_STRUCTURE

Unit 9: Recursion

9.1.1 Definition of Recursion
A function that calls itself is termed as a recursive function and the process involved in doing this is
called recursion. Recursion is a methodology that permits breaking down of a problem into one or
many sub problems that are similar to the original problem.
The parameters defined in the function definition are termed as formal arguments. The parameters
defined in a caller function and provided in the function call are termed as local variables Every time a
function is invoked, a new set of formal parameters and local variables are allocated on the stack. Then,
these new values are used to execute from the beginning of the function. A call to itself repeats until the
base or terminal condition is achieved. Once the base condition is achieved, the function returns the
result of the earlier function. A series of returns ensure that the output to the original problem is
obtained.

A simple recursive example

/* A preprocessor directive */
#include<stdio.h>
/* printnum function definition */
int printnum (int begin)
{
/* If begin value is less than 9 */
if (begin < 9)
{
/* Print begin value */
printf (%d”, begin);
/* printnum function calls itself */
printnum (begin + 1);
}
/* Return begin value */
return (begin);
}

/* Main function */
void main ()
{
/* Initialize integer variables a and c and assign 1 to a */
int a=1, c;
/* Clears the output screen */
clrscr ();
/* Calls printnum function passing the parameter 1*/
c = printnum (a);
/* Waits until a key is pressed */
getch();
}
Output:
12345678
In this example:

1. First, the stdio.h header file is included using the include keyword.
2. Then, a function named printnum is declared which returns an
integer value stored in begin.
3. In this method,
(a) First, the value of begin using an ‘if’ condition is checked to
determine whether it is less than 9. If the condition is true, begin

LOVELY PROFESSIONAL UNIVERSITY 153