Page 161 - DCAP407_DATA_STRUCTURE
P. 161
Data Structure
is printed and the printnum (begin + 1) function is invoked.
(b) Finally, the method returns the value of begin.
4. Execution begins with the function main () which does not return any
value.
5. In the main() function,
(a) First, integer variables a and c are initialized and value 1 is
assigned to a.
(b) Then, output screen is cleared using clrscr ().
(c) Then, a parameter named a, which holds the value 1, is passed
into the printnum function. This value is stored in variable c.
Finally, the program terminates when any key is pressed.
The functions that are generally defined recursively are:
1. Factorial
2. Greatest Common Divisor (GCD)
3. Fibonacci
4. Games
(a) Chess
(b) Towers of Hanoi
To successfully apply recursion to a problem, you should be able to divide the problem into subparts,
which is as shown in the problem given below.
For instance, we can compute the positive exponential power of a using recursion.
b
The recursive definition for finding a positive exponential power of a given number is as follows:
; 1 if b = 0
Power (a ,b ) =
1
a ∗ power (a ( , b − )); if b > 0
Here, ‘a’ is the mantissa and ‘b’ is the exponent.
In the same manner, you can determine the negative exponential power of number, such as, a . The
-b
definition of recursion is as follows:
; 1 if b = 0
b
Power (a , − ) =
1
1 /(a ∗ power (a ( , b − ))); if b > 0
Here, the power is negative, therefore, the inverse return value of a function is considered to be the
exponential power of the number. That is, a = 1 / a .
-b
b
Let us now consider an example that recursively computes power (x, y) such that the value contained in
x is raised to y power.
th
A recursive routine that computes the value of 5 raised to the power of 2, i.e.,
power (5, 2).
/* A recursive function that returns the result of the value raised to the power
contained in the variable raised*/
/* It returns 0 or -1 if the raised value is negative*/
/* A preprocessor directive */
154 LOVELY PROFESSIONAL UNIVERSITY
