3 Recursion – Introduction to Data Structures in C

Chapter 3

Recursion

Chapter Outline

3.1 INTRODUCTION TO FUNCTION

A function is a block of statements that can be used to perform a specific task. Fig. 3.1 describes the various parts of the function. A function has the following parts:

  1. Function prototype declaration
  2. Definition of a function (function declarator)
  3. Actual and formal arguments
  4. Return statement
  5. Invoking function.

3.1.1 Function Prototypes

We use many built-in functions. The prototypes of these functions are given in the respective header files. We include them using # include directive. In C++, while defining user-defined functions, it is unavoidable to declare its prototype. A prototype statement helps the compiler to check the return and argument types of the function.

A function prototype declaration consists of function’s return type, name, and arguments list. It tells the compiler:

  1. Name of the function
  2. Type of value returned
  3. The type and number of arguments.

Figure 3.1 Parts of function

When the programmer defines the function, the definition of function must be similar to its prototype declaration. If the programmer makes a mistake, the compiler flags an error message. The function prototype declaration statement is always terminated with a semi-colon. The statements given below are examples of function prototypes.

In example (A) the return type is void, i.e. the function will not return any value. The void functions are always without return statement. The argument void indicates the function will not require any argument. By default, every function returns an integer value. To return a noninteger value, the data type should be mentioned in function prototype and definition. While writing definition of function, the return type must be preceded by the function name and it is optional if return type is default (int).

In example (B) the prototype of function sum () is declared. Its return type is float and arguments are float and integer type, respectively. It is shown in the Fig. 3.1.

In example (C) with argument type, argument names are also declared. It is optional and not compulsory to use the same variable name in the program.

3.1.2 Function Definition

The first line is called as function declarator and then function body follows it. The block of statements followed by function declarator is called as function definition. The declarator and function prototype declaration should match with each other. The function body is enclosed within curly braces. The function can be defined anywhere. If the function is defined before its caller, then its prototype declaration is optional.

3.1.3 Function Call

A function is a latent body. It is activated only when a call to function is invoked. A function must be called by its name followed by argument list enclosed in parenthesis and terminated by semi-colon.

3.1.4 Actual and Formal Argument

The arguments declared in caller function and given in the function call are called as actual arguments. The arguments declared in the function declarator are known as formal arguments. For example,

Figure 3.2 Actual and formal arguments

As shown in Fig. 3.2, variable y and z are actual arguments and j and k are formal arguments. The values of y and z are stored in j and k, respectively. The values of actual arguments are assigned to formal arguments. The function uses formal arguments for computing.

3.1.5 The Return Statement

The return statement is used to return value to the caller function. The return statement returns only one value at a time. When a return statement is encountered, the compiler transfers the control of the program to caller function. The syntax of return statement is as follows:

return (variable name); or return variable name;

The parenthesis is optional.

3.2 TYPES OF RECURSIONS

Recursion a little bit tough, but if we keep track of the program, in which sequence it is executing, it is easy to understand. Recursion is one of the most dominant tools used in the programming technique. There are various situations when we need to execute a block of statements for a number of times depending on condition at that time recursion is useful. Recursion is used to solve a problem, which has iterations in reverse order. Data structures also support recursion, for example, tree supports recursion. Various programs are solved with the use of recursion. The major application of recursion is game programming where series of steps can be solved with recursion.

When a function calls itself recursively it is known as recursion. Recursion is of two types:

  1. Direct recursion
  2. Indirect recursion.

The recursion in which the function calls itself is called direct recursion. In this type, only one function is involved. In indirect recursion two functions call each other. Fig. 3.3 describes direct and indirect recursion.

Figure 3.3 Types of recursions

Recursion is one of the applications of stack. Stacks are explained in the next chapter. There are several problems in which without recursion their solution is lengthy.

The programming languages like C, C++ allow us to define user defined functions. Functions in the programming languages are very useful, because by using function a separate block of statements can be defined. This block can be invoked a number of times anywhere in the program. A function which can call itself or another function and which eventually calls another function is known as recursive function.

Two essential conditions should be satisfied by a recursive function. First, every time a function should call itself directly or indirectly. Second, the function should have a condition to stop the recursion. Otherwise, an infinite loop is generated that will halt the system.

Some people think that recursion is a very needless luxury in the programming language. Using iteration one can solve the problems. However, in programming in some situation there is no substitute for recursion.

There are some kinds of problems associated with recursive function which are not present in the non-recursive function. The recursive function can be invoked by itself or any other function. To make sure execution it is very essential for the function to save the return address in order to return to proper location. Also, the function has to save the formal and local variables.

Example 3.1

Write a program to calculate factorial of given number using recursion using C statements

Solution

# include <stdio.h>

# include <conio.h>

int fact (int);

main ()

{

int num,f;

clrscr();

printf ("\n Enter a number: ");

scanf ("%d",&num);

f=fact(num);

    printf ("\n Factorial of %d is %d",num,f);

}

int fact(int f)

{

    if (f==1) return f;

else return f*fact(f−1);

}

OUTPUT

Enter a number: 4

Factorial of 4 is 24

Explanation In this program fact () is a recursive function. The entered number is passed to function fact (). When function fact () is executed, it is repeatedly invoked by itself. Every time a function is invoked, the value off is reduced by one and multiplication is carried. The recursive function produces the numbers 4,3,2 and 1. The multiplication value of these numbers is taken and returned to main () function.

3.3 RULES FOR RECURSIVE FUNCTION
  1. In recursion, it is essential for a function to call itself, otherwise recursion will not take place, as shown in Fig. 3.3.
  2. Only user defined function can be involved in the recursion. Library function cannot be involved in recursion because their source code cannot be viewed.
  3. A recursive function can be invoked by itself or by other function. It saves return address in order with the intention that to return at proper location when return to a calling statement is made. The last-in-first-out nature of recursion indicates that stack data structure can be used to implement it.
  4. Recursion is turning out to be increasingly important in non-numeric applications and symbolic manipulations.
  5. To stop the recursive function it is necessary to base the recursion on test condition and proper terminating statement such as exit () or return must be written using if () statement as shown in the Fig. 3.4.

    Figure 3.4 Terminating statement in recursion

  6. The user defined function main () can be invoked recursively. To implement such recursion it is necessary to mention prototype of function main (). An example in this regard is explained as follows:

    Example 3.2

    Write a program to call main () recursively.

    Solution

    # include <stdio.h>

    # include <conio.h>

    # include <process.h>

    char str[]="Have a Good Day";

    int x=0;

    main();

    void main ()

    {

    switch(str[x])

    {

        case 'H':

        clrscr();

        default:

        printf ("%c",str[x]);

        break;

        case '\0':

        exit(0);

        break;

    }

    x++;

    main();

    }

    OUTPUT

    Have a Good Day

    Explanation In this program main () function is invoked recursively. A prototype of function main () is given before function definition. However, in normal practice it is not necessary to give prototype. A recursive function must know its return type and number and type of the arguments passed.

     

  7. Any function can be called recursively. An example is illustrated as above.
  8. When a recursive function is executed, the recursion calls are not implemented instantly. All the recursive calls are pushed onto the stack until the terminating condition is not detected. As soon as the terminating condition is detected, the recursive calls stored in the stack are popped and executed. The last call is executed first then second, then third and so on.
  9. During recursion, at each recursive call new memory is allocated to all the local variables of the recursive functions with the same name.
  10. At each call the new memory is allocated to all the local variables, their previous values are pushed onto the stack and with its call. All these values can be available to corresponding function call when it is popped from the stack.
3.4 DIRECT RECURSION

In this type, only one function is involved which calls itself until the given condition is true. Consider the following program:

Example 3.3

Write a program call function main () and perform sum of first five numbers.

Solution

# include <stdio.h>

# include <process.h>

void main (int);

int x,s;

void main (x)

{

s=s+x;

printf ("\n x=%d s=%d",x,s);

if (x==5) exit(0);

main (++x);

}

OUTPUT

x=1 s=1

x=2 s=3

x=3 s=6

x=4 s=10

x=5 s=15

Explanation In this program variable x and y are declared outside main (). Initially their values are zero. The prototype if function main () is declared. This is essential because while calling, the compiler checks the function with its prototype. It is advance information regarding the function. The variable x is passed to the function main (). The variable x is added to variable s until the value of x reaches to five. When x reaches to five, the program terminates.

 

Table 3.1 Steps of recursive function

Function Call Value of x Value of s (sum)
main(1)
x=1
s=1 (0+1)
main(2)
x=2
s=3 (2+1+0)
main(3)
x=3
s=6 (3+2+1+0)
main(4)
x=4
s=10 (4+3+2+1+0)
main(5)
x=5
s=15 (5+4+3+2+1+0)

Example 3.4

Write a program to calculate triangular number using recursion.

Solution

# include <stdio.h>

# include <conio.h>

# include <process.h>

main ()

{

int trinum(int );

int t,x;

clrscr();

printf ("\n Enter a Number: ");

scanf ("%d",&x);

t=trinum(x);

printf ("\n Triangular Number of %d is %d",x,t);

}

int trinum(int x)

{

int f=0;

if (x==0) return f;

else f=f+x+trinum(x−1);

return f;

}

OUTPUT

Enter a Number: 4

Triangular Number of 4 is 10

Explanation In this program a function trinum () is defined which calls itself. An integer is entered through the keyboard and it is stored in the variable x. The function trinum () calls itself and the argument passed to this called function is one less than the value of x. The return values are added to variable f. When value of x becomes zero, the recursion ends and the total is returned to variable t in function main (). The value of t is triangular number of the entered number, which is nothing but the sum of all the integers between 1 to the entered number. The recursive function is called repetitively by itself without completing the execution of previous call. When program ends and the control is about to return to caller function the number of times the return statement executed is equal to the number of times the function is called recursively. The compiler keeps track of how many times a function is executed. To see, these points execute the program in single step by pressing F7 key.

 

When a function returns three actions are done. The return address is placed in the safe location. The data stored in local variables of function are freed. The previously saved address is retrieved. The return value of function is returned and put in the safe location and calling program receives it. Normally, the location is a hardware register, which is placed in CPU for the same purpose.

Figure 3.5 Functions calling one another

As shown in the above Fig. 3.5 the main function call invokes the function B. The function B invokes the function C and again C invokes D. The figure shows the control is present in the function D. In every function, a location is reserved for storage of return address. The return address location of function D contains the address of statement in C immediately after the function invocation statement.

Whenever a recursive function invokes itself, new data variables are created and memory is allocated for data. The data area contains all local variables and return address. In the recursion function, the data area is not connected only with the function but closely associated with the particular function call. In every call new data area is allocated and the particular function’s data area contains information about recent call. Every time control returns, the data area is de-allocated or freed and the former data area turn into current.

The recursion in C and C++ language is more expensive as compared to non-recursive function. It takes not only more space but it is also time consuming. In some system program such as compiler or operating system, if program contains recursive function it will be executed many a time. In such a case, an alternate non-recursive function may be defined.

Example 3.5

Write a program to define to a recursive function to calculate factorial of a number.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

int fact(int);

int f,n;

clrscr();

printf ("\n Enter a Number: ");

scanf ("%d",&n);

f=fact(n);

printf ("Factorial of Number %d: %d",n,f);

}

int fact (int j)

{

int f=1;

if (j==1)

return 1;

else

f=j*fact(j−1);

return f;

}

OUTPUT

Enter a Number: 5

Factorial of Number 5: 120

Explanation In this program function fact () is defined and the number entered by the user is passed to the function fact (). In the function fact () the if statement checks the value of variable j (formal argument of n). If the value is 1 the return statement returns 1 otherwise the fact () function is called. At this point, the recursion actually begins. When the function fact () is recursively invoked the value of j is decreased by one and then passed.

3.5 INDIRECT RECURSION

In this type of recursion two or more functions are involved in the recursion. The indirect recursion does not make any overhead as direct recursion. When control exits from one function and enters into another function, the local variables of former function are destroyed. Hence, memory is not engaged. The following program explains the indirect recursion.

Example 3.6

Write a program to demonstrate recursion between two functions.

Solution

# include <stdio.h>

# include <conio.h>

#include <process.h>

int s;

void show(void);

main()

{

if (s==5) exit(0);

show ();

}

void show ()

{

printf ("%d",s);

s++;

main();

}

OUTPUT

0 1 2 3 4

Explanation In this program two user defined functions are defined main () and show (). The s is global variable. The main () function invokes show () function and the show () function invokes main () function. The value of s is increased and displayed. When value of s reaches to 5 the program is terminated.

Example 3.7

Write a program to display numbers in several rows.

Solution

# include <stdio.h>

# include <conio.h>

# include <process.h>

int s;

void show(void);

main()

{

if (s==0)

clrscr();

if (s==10)

exit(0);

show ();

}

void show ()

{

int j;

for (j=0;j<=s;j++)

printf ("%d",j);

printf ("\n");

s++;

main();

}

OUTPUT

0

0 1

0 1 2

0 1 2 3

0 1 2 3 4

0 1 2 3 4 5

0 1 2 3 4 5 6

0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7 8

0 1 2 3 4 5 6 7 8 9

Explanation This program is same as the last one. Here, depending on the value of variable s, the iteration of for loop is performed.

3.6 RECURSION VS. ITERATIONS

We have studied both recursion and iteration. They can be applied to a program depending upon the situation. Table 3.2 explains the differences between recursion and iteration.

 

Table 3.2 Recursion Vs. Iteration

Recursion Iteration
Recursion is the term given to the mechanism of defining a set or procedure in terms of itself. The block of statement executed repeatedly using loops.
A conditional statement is required in the body of the function for stopping the function execution. The iteration control statement itself contains statement for stopping the iteration. At every execution, the condition is checked.
At some places, use of recursion generates extra overhead. Hence, better to skip when easy solution is available with iteration. All problems can be solved with iteration.
Recursion is expensive in terms of speed and memory. Iteration does not create any overhead. All the programming languages support iteration.

Figure 3.6 illustrates the iterative process.

Initialization The variables involved in the iteration process are initialized. These variables are used to decide when to end the loop.

Figure 3.6 Iterative processes

Decision The decision variable is used to decide whether to continue or discontinue the loop. When the condition is satisfied, control goes to return, or else it goes to computation block.

Computation The required processing or computation is carried out in this block.

Update The decision argument is changed and shifted to next iteration.

The common algorithm for any kind of recursive function is shown in Fig. 3.7.

Preliminary part The use of this block is to store the local variables, formal arguments and return address. The end-part will restore these data. Only recently saved arguments, local variables and return address are restored. The variables last saved are restored first.

Body If the test condition is satisfied, it performs the complete processing and control passes to end-block. If not, partial processing is performed and a recursive call is made. The body also contains call to itself and one or more calls can be made. Every time a recursive call is made, the preliminary part of the function saves all the data. The body also contains two processing boxes i.e. partial processing and complete processing. In some programs, the result can be calculated after complete processing. For this, the recursive call may not be required. For example, we want to calculate factorial of one. The factorial of one is one. For this, it is needless to call function recursively. It can be solved by transferring control to complete processing box.

Figure 3.7 Recursive process

In other case, if five is given for factorial calculation, the factorial of five can be calculated in one step. Hence, the function will be called recursively. Every time one step is solved, i.e. 5*4*3 and so on. Hence, it is called partial processing.

Depth of Recursion The recursion function calls itself infinite times. If we want to calculate factorial of five then we can easily estimate the number of times the function would be called. In this case, we can determine the depth of the recursive function. In complex program, it is difficult to determine the number of calls of recursive function.

3.7 THE TOWERS OF HANOI

The Tower of Hanoi has historical roots in the ceremony of the ancient tower of Brahma. There are n disks of decreasing sizes mounted on one needle as shown in the Fig. 3.8(a). Two more needles are also required to stack the entire disk in the decreasing order. The use of third needle is for impermanent storage. While mounding the disk, following rules should be followed.

  1. At a time only one disk may be moved.
  2. The disk may be moved from any needle to another needle.
  3. No larger disk may be placed on the smaller one.

Our aim is to move the disks from A to C using the needle B as an intermediate by obeying the above three conditions. Only top-most disks can be moved to another needle. The following figures and explanation clear the process of Tower of Hanoi stepwise.

Figure 3.8 (a) Recursive Towers of Hanoi

In Fig. 3.8 (a), the three needles are displayed in their initial states. The needle A contains five disks and there are no disk on needle B and C. The arrow indicates the next operation to be performed, i.e. move first four disk from A to C.

Figure 3.8 (b) Recursive Towers of Hanoi

In Fig. 3.8(b) the needle, A has only one disk. The needle C contains four disks. The arrow indicates the next operation, i.e. move four disks from C to B.

Figure 3.8 (c) Recursive Towers of Hanoi

In Fig. 3.8(c), the needle B has four disks. The needle A has only one disk, which will be moved to needle C.

Figure 3.8 (d) Recursive Towers of Hanoi

In Fig. 3.8(d), the needle A has no disk. The needle B contains four disks and C contains one disk. The four disks move from B to A.

Figure 3.8 (e) Recursive Towers of Hanoi

In Fig. 3.8(e), the four disks from needle A are moved to needle C. Finally, the final position of needles A, B and C will be as shown in Fig. 3.8(f). Here, solution of Tower of Hanoi is complete.

Figure 3.8 (f) Recursive Towers of Hanoi

The above process can be summarized as:

  1. Move first four disks from needle A to C
  2. Move four disks from C to B
  3. Move the disk one from A to C
  4. Move four disks from B to A
  5. Move four disks from A to C.

Example 3.8

Write a program to illustrate Towers of Hanoi.

Solution

# include <conio.h>

# include <stdio.h>

void hanoi (int,char,char,char);

main ()

{

int num;

clrscr();

printf ("\n Enter a Number: ");

scanf ("%d",&num);

clrscr();

hanoi(num,'A','C','B');

}

void hanoi( int num, char f_peg, char t_peg, char a_peg)

{

if (num==1)

{

    printf ("\nMove disk 1 from Needle %c to Needle %c",f_peg,t_peg);

    return;

}

hanoi(num−1,f_peg,a_peg,t_peg);

printf ("\nMove disk %d from Needle %c to Needle %c",num,f_peg,t_peg);

hanoi(num−1,a_peg,t_peg,f_peg);

}

OUTPUT

Move disk 1 from Needle A to Needle C

Move disk 2 from Needle A to Needle B

Move disk 1 from Needle C to Needle B

Move disk 3 from Needle A to Needle C

Move disk 1 from Needle B to Needle A

Move disk 2 from Needle B to Needle C

Move disk 1 from Needle A to Needle C

Explanation In the above program numbers of disks are entered. The function Hanoi () is invoked from main (). The A, B and C are needles. If value of num is one, the disk is transferred from A to C and program ends. If the value of num is greater than one, then the Hanoi () function invokes itself recursively, every time value of num is decreased by one. The output of the program is shown as above.

3.8 ADVANTAGES & DISADVANTAGES OF RECURSION

Advantages of recursion,

  1. Sometimes, in programming a problem can be solved without recursion, but at some situations in programming it is must to use recursion. For example, a program to display the list of all files of the system cannot be solved without recursion.
  2. The recursion is very flexible in data structure like stacks, queues, linked list and quick sort.
  3. Using recursion, the length of the program can be reduced.

Disadvantages of recursion,

  1. It requires extra storage space. The recursive calls and automatic variables are stored on the stack. For every recursive call separate memory is allocated to automatic variables with the same name.
  2. If the programmer forgot to specify the exit condition in the recursive function, the program will execute out of memory. In such a situation user has to press ctrl+ break to pause or stop the function.
  3. The recursion function is not efficient in execution speed and time.
  4. If possible, try to solve problem with iteration instead of recursion.
3.9 TAIL RECURSION

In this chapter we have studied the recursion and we can say that recursion is a method in which set of process is given in terms of itself. Recursive function is invoked by itself and this function call is given in the same function body. If the function call statement is the last statement in the function body, this recursion is called tail recursion. In tail recursion, we can use return value as a parameter for the function. All the functions are maintained using stack, however, in this type, it will not push new function call to stack but it will replace the value of previous call with new call. This approach provides decreased stack implementation time and gives faster execution. The program 3.7 is an example of tail recursion.

3.10 EFFICIENCY OF RECURSION

We have studied both advantages and disadvantages of recursion. We have also studied the iteration which is an alternative to recursion. The major overhead of recursion is the memory it occupies and execution time. A non-recursive function will require minimum memory and less time for execution as compared with recursive function. The recursive function uses stack to push and pop the local variables. In non-recursive function the above push and pop operations with stack can be skipped. However, at some situation in programming use of recursion is must. If the part of program is to be invoked frequently, in such a case it is better to develop non-recursive function.

Summary
  1. A function is a block of statements that can be used to define to perform a special task.
  2. A function prototype declaration consists of function’s return type, name, and arguments list. It tells the compiler, a) name of the function, b) type of value returned, c) the type and number of arguments.
  3. When a function calls itself is called direct recursion.
  4. When a function calls another function it is called indirect recursion
  5. The user defined function main () can be invoked recursively. The library functions cannot be invoked recursively.
  6. Constructor is a special member function used to initialize the data members. The constructor can also be invoked recursively.
  7. Whenever a recursive function invokes itself, every time new data variables are created and data area and memory is allocated. The data area contains all local variables and return address. In the recursion of function, the data area is not connected only with the function but closely associated with the particular function call.
Exercises
  1. Answer the following questions:
    1. Explain recursion process in detail.
    2. Differentiate between direct and indirect recursions.
    3. Differentiate between recursion and iteration.
    4. Mention the advantages and disadvantages of recursions.
    5. List the three rules of tower of Hanoi problem.
    6. What is depth of recursion?
    7. Explain tail recursion.
  2. Attempt following program with recursion:
    1. Write a program to compute the nth number of fibonacci series.
    2. Write a program to reverse a number.
    3. Write a program to display list of prime numbers up to 15.
    4. Write a program to display a message "Hello" for 10 times.
    5. Write a program to call function main () recursively.
    6. Write a program to demonstrate tail recursion.
    7. Consider the following list

      58,69,59,12,34,78,25,98,20

      1. Find elements 34,25 and 20 using recursion
      2. Calculate product of all elements of array
      3. Sum of all the elements.
  3. Select the appropriate option for each of the following questions:
    1. When a function calls itself is called
      1. Recursion
      2. iteration
      3. function
      4. none of the above.
    2. In indirect recursion a function calls
      1. another function
      2. itself
      3. only main () function
      4. none of the above.
    3. In tower of Hanoi the following one condition is not applicable:
      1. at a time only one disk may be moved
      2. the disc may be moved from any needle to another needle
      3. No larger disk may be placed on the smaller one
      4. The disks can be placed in any order.
    4. The function declarator is used to
      1. declare formal arguments
      2. declare function prototype
      3. function call
      4. all of the above.
  4. What will be the output of the following programs:
    1. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      int main (void);

      printf ("\n Hello");

      return (main ());

      }

       

    2. # include <stdio.h>

      # include <conio.h>

      int x;

      int main ()

      {

      clrscr();

      int num(void);

      printf (" %d ",num());

      return 0;

      }

      int num()

      {

      x++;

      if (x>8) return x;

      else

      return main();

      }

       

    3. # include <stdio.h>

      # include <conio.h>

      int main ()

      {

      int num (void);

      clrscr();

      int n[]={num()};

      for (int i=0;i<3;i++)

      printf (" %d ",n[i]);

      return 0;

      }

      int num ()

      {

      int x;

      printf ("\n Enter a number: ");

      scanf ("%d",&x);

      if (x==0)

      return x;

      num();

      return x;

      }

       

    4. # include <stdio.h>

      # include <conio.h>

      void show(void);

      main()

      {

      clrscr();

      show ();

      }

      void show ()

      {

      int i,j;

      for (i=0;i<=5;i++)

      for (j=0;j<=i;j++)

      printf ("%d",j);

      printf ("\n");

      }

       

    5. # include <stdio.h>

      # include <conio.h>

      void dis();

      int k=9

      main()

      {

      clrscr();

      dis();

      k=100;

      printf("%d",k);

      }

      void dis()

      {

      printf ("%d",k);

      }

       

    6. # include <stdio.h>

      # include <conio.h>

      void fun(int);

      void fun1(int);

      void fun2(int);

      main()

      {

      int a=109;

      clrscr();

      fun(a);

      fun1(a);

      fun2(a);

      }

      void fun (int a)

      { printf ("%d",a++); }

      void fun (int a)

      { printf ("%d",a—); }

      void fun (int a)

      { printf ("%d",a++); }