Page 163 - DCAP407_DATA_STRUCTURE

Data Structure

5. In main(),
(a) First, the integer variables x, y and z are initialized.
(b) The output screen is cleared using clrscr ().
(c) The base value is accepted and stored in x.

(d) The exponent value is accepted and stored in y.
(e) The power function is called with the arguments x and y. The value
returned is assigned to z.
(f) The value of z is printed.
(g) Finally getch() prompts the user to press any key and the program
terminates.

Now let us consider how we solve 5 * power (5, 2). If power() function is called for power(5, 2), the
processing performed is as shown below.
power (5, 2) return (5 * power (5, 2-1))
power (5, 1) return (5 * power (5, 1-1))
power (5, 0) return 1 as any value that is raised to zero is one

The expression a % b yields the remainder of ‘a’ divided by ‘b’. Greatest common
divisor (GCD) of integers x and y is defined as:
If (y <=x && x % y == 0); gcd (x, y) = y
If (x < y); gcd (x, y) = gcd (y, x)
Otherwise; gcd (x, y) = gcd (y, x % y)

Write a recursive function in C to determine gcd (x, y). Also determine an iterative
method to compute this function.

9.1.2 Types of Recursion
When a function invokes itself, it is called as recursion. There are two types of recursion. They are:
1. Direct Recursion: In this kind of recursion, the function invokes itself. Direct recursion involves
only one function.
2. Indirect Recursion: Indirect recursion occurs when one method invokes the other, which
eventually results in the original method being called again.
Direct Recursion
Direct recursion involves only one function that invokes itself till the specified condition is true. Let us
analyze the following program:

A program that performs sum of first five numbers using a call function

/* A preprocessor directive to include standard input and output operations */
# include <stdio.h>
/* A preprocessor directive that contains macros and function declaration used in
working with processes and threads */
# include <process.h>
/* Globally declare the main function */
void main (int);
/* Initialize integer variables x and s and assign 0 to s */
int x, s = 0;

156 LOVELY PROFESSIONAL UNIVERSITY