Page 166 - DCAP407_DATA_STRUCTURE

Unit 9: Recursion

A recursive case defines a problem in terms of smaller problems of similar type. Recursive case
comprises a recursive function call. A problem can consist of many recursive cases.
To determine recursive solution for any kind of problem, follow the steps given below:

1. Define a problem in terms of a smaller problem of similar type.
2. Define recursive part. In the power() function shown in 9.1.1, the statement ‘return (x * power (x, y
– 1))’; is the recursive part.
3. Define base case even for a small problem where solution can be calculated easily.
To attain recursive solutions, follow the steps given below:

1. Analyze how the problem can be defined in terms of smaller problems.
2. Determine how each of the recursive calls help to divide the problem into sub-problems.
3. Analyze the base case which can be solved without recursion.
4. Find whether the base case can be attained or not when the problem is broken.

Be careful while using recursive step. If the terminal or base condition is omitted and the
recursive step is wrongly used, then it will result in infinite recursion that exhausts the
memory slowly.
Let us design a recursive solution for writing a string backwards.

Problem: Write a string of characters in reverse order.
Recursive solution: Write the last character of string and solve the problem by writing the first (n-1)
character backward. Each recursive solution should increment the string pointer of the string that needs
to be written backwards. Then, define the base case by writing an empty string backward which does
not do anything. As the problem reduces, the base case is attained.

Program to write a string of characters in reverse order
/* A preprocessor directive that contains standard input and output operations */
#include<stdio.h>
/* print_reverse is a recursive function which takes variable S */
print_reverse (char *S)
/* S is a pointer which points to a character */
{

/* Check whether the string pointer value is not equal to NULL*/
if (*S != NULL)
{
/* print_reverse function calls itself after incrementing the pointer by 1
*/

print_reverse (++S);
/* putchar writes a single character to the standard output stream, that
is, the value of S is decremented and that string pointer is written*/
putchar (* (--S));
}

/* Main function */

LOVELY PROFESSIONAL UNIVERSITY 159