UNIT 2

Control Structures

2.1 Control Structures

Control Structures are just a way to specify flow of control in programs. Any algorithm or program can be clearer and more understood if they use self-contained modules called as logic or control structures. It basically analyses and chooses in which direction a program flows based on certain parameters or conditions. There are three basic types of logic, or flow of control, known as:

1. Sequence logic, or sequential flow
2. Selection logic, or conditional flow
3. Iteration logic, or repetitive flow

Let us see them in detail:

1. Sequential Logic (Sequential Flow)

Sequential logic as the name suggests follows a serial or sequential flow in which the flow depends on the series of instructions given to the computer. Unless new instructions are given, the modules are executed in the obvious sequence. The sequences may be given, by means of numbered steps explicitly. Also, implicitly follows the order in which modules are written. Most of the processing, even some complex problems, will generally follow this elementary flow pattern.

Sequential Control flow

2.     Selection Logic (Conditional Flow)

Selection Logic simply involves a number of conditions or parameters which decides one out of several written modules. The structures which use these type of logic are known as Conditional Structures. These structures can be of three types:

• Single Alternative This structure has the form:
• If (condition) then:
• [Module A]  

[End of If structure]

• Double Alternative This structure has the form:
• If (Condition), then:
• [Module A]
• Else:
• [Module B]
• [End if structure]
• Multiple Alternatives This structure has the form:
• If (condition A), then:
• [Module A]
• Else if (condition B), then:
• [Module B]
• ..
• ..
• Else if (condition N), then:
• [Module N]
• [End If structure]

In this way, the flow of the program depends on the set of conditions that are written. This can be more understood by the following flow charts:

Double Alternative Control Flow

3.     Iteration Logic (Repetitive Flow)
The Iteration logic employs a loop which involves a repeat statement followed by a module known as the body of a loop.
The two types of these structures are:

• Repeat-For Structure
  This structure has the form:
• Repeat for i = A to N by I:
• [Module]
• [End of loop]

Here, A is the initial value, N is the end value and I is the increment. The loop ends when A>B. K increases or decreases according to the positive and negative value of I respectively.

Repeat-For Flow

• Repeat-While Structure
  It also uses a condition to control the loop. This structure has the form:
• Repeat while condition:
• [Module]
• [End of Loop]

Repeat While Flow

2.2 Basic input and output statements

The C language is accompanied by a collection of library functions which includes a  number of input/output functions. These functions are used to permit the transfer  of information between the computer and the standard input/output device. The basic input/output functions  are getchar, putchar, puts, scanf and printf. The first two functions, getchar and putchar, are used to transfer single characters. The next function puts is used to output strings, and the last two functions, scanf and printf, permit the transfer of single characters, numerical values and strings.

An input/output function can be accessed from anywhere within a program simply by writing the function name, followed by a list of arguments enclosed in parentheses. The arguments represent data items that are sent to the function. Some input/output functions do not require arguments, though the empty parentheses must still appear.

The names of those functions that return data items may appear within expressions, as though each function reference were an ordinary variable (eg, c=getchar();), or they may be referenced as separate statements (eg, scanf(...);). Some functions do not return any data items. Such functions are referenced as though they were separate statements (eg, putchar(...);).

C includes a collection of header files that provide necessary information in support of the various library functions. Each file generally contains information in support of a group of related library functions. These files are entered into the program via an #include statement at the beginning of the program. As a rule, the header file required by the standard input/output library functions is called stdio.h.

Single Character Input: the getchar Function

The getchar function is a part of the standard C input/output library. It returns a single character from a standard input device (typically a keyboard). The function does not require any arguments, though a pair of empty parentheses must follow the word getchar.

In general, a function reference would be written as:

Character variable = getchar( );

Where character variable refers to some previously declared character variable.

If an end-of-file condition is encountered when reading a character with the getchar function, the value of the symbolic constant EOF will automatically be returned. (This value will be assigned within the stdio.h file. Typically, the EOF will be assigned the value -1). The detection of EOF in this manner offers a convenient way to detect an  end of file, whenever and wherever it may occur. Appropriate corrective action may then be taken.

The getchar function can also be used to read multi-character strings by reading one character at a time within a multi-pass loop.

Single Character Output: the putchar Function

Single characters can be displayed using the C library function putchar. This function is complementary to the character input function getchar.

The putchar function like getchar is a part of the standard C input/output library. It transmits a single character to the standard output device (the computer screen). The character being transmitted will be represented as a character-type variable. It must be expressed as an argument to the function, enclosed in parentheses, following the word putchar.

In general, a function reference would be written as:

Putchar(character variable)

Where character variable refers to some previously declared character variable.

A simple example demonstrating the use of getchar and putchar is given below:

#include<stdio.h>

Int main()

{

Char c;

Printf("n Please enter a character:");

c=getchar();

Printf("n the character entered is: ");

Putchar(c);

Return 0;

}

In the above program, the statement c=getchar(); accepts a character entered by the user and stores it in the variable c. The character entered by the user can be anything from the C character set. The statement putchar(c); prints the character stored in the variable c.

The putchar function can be used to output a string constant by storing the string within a one-dimensional character-type array. Each character can then be written separately within a loop. The most convenient way to do this is to utilize the for statement, which we will discuss in future.

Entering Input Data: the scanf Function

Input data can be entered from a standard input device by means of the C library function scanf. This function can be used to enter any combination of numeric values, single characters and strings. The function returns the number of data items that have been entered successfully.

In general terms, the scanf function is written as:

Bottom of Form

Scanf(control string, arg1, arg2,.........,argN)

Where control string refers to a string containing certain required formatting information, and arg1,arg2,….,argN are arguments that represent the individual data items. (Actually, the arguments represent pointers that indicate the addresses of the data items within the computer’s memory. We will discuss pointers in greater detail in a future article, but until then it would be helpful to remember the fact that the arguments in the scanf function actually represent the addresses of the data items being entered.)

The control string consists of the individual group of characters called format specifiers, with one character group for each input data item. Each character group must begin with a per cent sign (%) and be followed by a conversion character which indicates the type of the data item. Within the control string, multiple character groups can be contiguous, or they can be separated by whitespace characters (i.e., white spaces, tabs or newline characters).

The most commonly used conversion characters are listed below:

Conversion Character     Data type of input data

c                        character

d                        decimal integer

e                        floating point value

f                        floating point value

g                        floating point value

h                        short integer

i                        decimal, hexadecimal or octal integer

o                        octal integer

x                        hexadecimal integer

s                        string

u                        unsigned decimal integer

[. . .]                  string which may include whitespace characters

The arguments to a scanf function are written as variables or arrays whose types match the corresponding character groups in the control string. Each variable name must be preceded by an ampersand (&). However, character array names do not begin with an ampersand. The actual values of the arguments must correspond to the arguments in the scanf function in number, type and order.

If two or more data items are entered, they must be separated by whitespace characters. The data items may continue onto two or more lines, since the newline character is considered to be a whitespace character and can therefore separate consecutive data items.

Example 1:

#include<stdio.h>

Int main()

{

Char a[20];

Int   i;

Float b;

Printf(" n Enter the value of a, i and b");

Scanf("%s %d %f", a, &i, &b);

Return 0;

}

In the above program, within the scanf function, the control string is "%s %d %f". It denotes three-character groups or format specifiers. The first format specifier %s denotes that the first argument a represents a string (character array), the second format specifier %d denotes that the second argument  i is an integer and the third format specifier %f denotes that the third argument b is a floating point number.

Also note that the only argument not preceded by an ampersand (&) is a since a denotes a character array.

The s-type conversion character applies to a string that is terminated by a whitespace character. Therefore, a string that includes whitespace characters cannot be entered in this manner. To do so, there are two ways:

1. The s-type conversion character is replaced by a sequence of characters enclosed in square brackets, designated as [. . .]. Whitespace characters are also included in the string so that a string that contains whitespaces may be read.

When the program is executed, successive characters will continue to be read as long as each input character matches one of the characters enclosed in the square brackets. The order of the characters in the square brackets need not correspond to the order of the characters being entered. As soon as an input character is encountered that does not match one of the characters within the brackets, the scanf function will stop reading any more characters and will terminate the string. A null character will then automatically be added to the end of the string.

Example:

#include<stdio.h>

Int main()

{

Char line[80];

Scanf(" %[  ABCDEFGHIJKLMNOPQRSTUVWXYZ]", line);

Printf("%s", line);

Return 0;

}

If the input data is:

READING A STRING WITH WHITE SPACES

Then the entire data will be assigned to the array line. However, if the input is:

Reading A String with White Spaces

Then only the letters in uppercase (R, A, S, W, S) will be assigned to line, as all the characters in the control string are in uppercase.

2. To enter a string that includes whitespaces as well as uppercase and lowercase characters we can use the circumflex, i.e. (^), followed by a newline character within the brackets.
Example:

Scanf("[^n]", line);

The circumflex causes the subsequent characters within the square brackets to be interpreted in the opposite manner. Thus, when the program is executed, characters will be read as long as a newline character is not encountered.

Reading Numbers: Specifying Field Width

The consecutive non-whitespace characters that define a data item collectively define a field. To limit the number of such characters for a data item, an unsigned integer indicating the field width precedes the conversion character. The input data may contain fewer characters than the specified field width. Extra characters will be ignored.

Example: If a and b are two integer variables and the following statement is being used to read their values:

Scanf( "%3d %3d", &a, &b);

And if the input data is: 1 4

Then a will be assigned 1 and b 4.

If the input data is 123 456 then a=123 and b=456.

If the input is 1234567, then a=123 and b=456. 7 is ignored.

If the input is 123 4 56 (space inserted by a typing mistake), then a=123 and b=4. This is because the space acts as a data item separator.

2.3 Pre-processor directives

The C Pre-processor is not a part of the compiler, but is a separate step in the compilation process. In simple terms, a C Pre-processor is just a text substitution tool and it instructs the compiler to do required pre-processing before the actual compilation. We'll refer to the C Pre-processor as CPP.

All pre-processor commands begin with a hash symbol (#). It must be the first nonblank character, and for readability, a pre-processor directive should begin in the first column. The following section lists down all the important pre-processor directives −

Pre-processors Examples

Analyse the following examples to understand various directives.

#define MAX_ARRAY_LENGTH 20

This directive tells the CPP to replace instances of MAX_ARRAY_LENGTH with 20. Use #define for constants to increase readability.

#include <stdio.h>

#include "myheader.h"

These directives tell the CPP to get stdio.h from System Libraries and add the text to the current source file. The next line tells CPP to get myheader.h from the local directory and add the content to the current source file.

#undef  FILE_SIZE

#define FILE_SIZE 42

It tells the CPP to undefine existing FILE_SIZE and define it as 42.

#ifndef MESSAGE

#define MESSAGE "You wish!"

#endif

It tells the CPP to define MESSAGE only if MESSAGE isn't already defined.

#ifdef DEBUG

/* Your debugging statements here */

#endif

It tells the CPP to process the statements enclosed if DEBUG is defined. This is useful if you pass the -DDEBUG flag to the gcc compiler at the time of compilation. This will define DEBUG, so you can turn debugging on and off on the fly during compilation.

Predefined Macros

ANSI C defines a number of macros. Although each one is available for use in programming, the predefined macros should not be directly modified.

Let's try the following example −

#include <stdio.h>

Int main() {

Printf("File :%s\n", __FILE__ );

Printf("Date :%s\n", __DATE__ );

Printf("Time :%s\n", __TIME__ );

Printf("Line :%d\n", __LINE__ );

Printf("ANSI :%d\n", __STDC__ );

}

When the above code in a file test.c is compiled and executed, it produces the following result −

File :test.c

Date :Jun 2 2012

Time :03:36:24

Line :8

ANSI :1

Preprocessor Operators

The C pre-processor offers the following operators to help create macros −

The Macro Continuation (\) Operator

A macro is normally confined to a single line. The macro continuation operator (\) is used to continue a macro that is too long for a single line. For example −

#define  message for(a, b)  \

Printf(#a " and " #b ": We love you!\n")

The Stringize (#) Operator

The stringize or number-sign operator ( '#' ), when used within a macro definition, converts a macro parameter into a string constant. This operator may be used only in a macro having a specified argument or parameter list. For example −

#include <stdio.h>

#define  message_for(a, b)  \

Printf(#a " and " #b ": We love you!\n")

Int main(void) {

Message_for(Carole, Debra);

Return 0;

}

When the above code is compiled and executed, it produces the following result −

Carole and Debra: We love you!

The Token Pasting (##) Operator

The token-pasting operator (##) within a macro definition combines two arguments. It permits two separate tokens in the macro definition to be joined into a single token. For example −

#include <stdio.h>

#define tokenpaster(n) printf ("token" #n " = %d", token##n)

Int main(void) {

Int token34 = 40;

Tokenpaster(34);

Return 0;

}

When the above code is compiled and executed, it produces the following result −

Token34 = 40

It happened so because this example results in the following actual output from the pre-processor −

Printf ("token34 = %d", token34);

This example shows the concatenation of token##n into token34 and here we have used both stringize and token-pasting.

The Defined() Operator

The pre-processor defined operator is used in constant expressions to determine if an identifier is defined using #define. If the specified identifier is defined, the value is true (non-zero). If the symbol is not defined, the value is false (zero). The defined operator is specified as follows −

#include <stdio.h>

#if !defined (MESSAGE)

#define MESSAGE "You wish!"

#endif

Int main(void) {

Printf("Here is the message: %s\n", MESSAGE); 

Return 0;

}

When the above code is compiled and executed, it produces the following result −

Here is the message: You wish!

Parameterized Macros

One of the powerful functions of the CPP is the ability to simulate functions using parameterized macros. For example, we might have some code to square a number as follows −

Int square(int x) {

Return x * x;

}

We can rewrite above the code using a macro as follows −

#define square(x) ((x) * (x))

Macros with arguments must be defined using the #define directive before they can be used. The argument list is enclosed in parentheses and must immediately follow the macro name. Spaces are not allowed between the macro name and open parenthesis. For example −

#include <stdio.h>

#define MAX(x,y) ((x) > (y) ? (x) : (y))

Int main(void) {

Printf("Max between 20 and 10 is %d\n", MAX(10, 20)); 

Return 0;

}

When the above code is compiled and executed, it produces the following result −

Max between 20 and 10 is 20

2.4 Functions: Concept of a function

In c, we can divide a large program into the basic building blocks known as function. The function contains the set of programming statements enclosed by {}. A function can be called multiple times to provide reusability and modularity to the C program. In other words, we can say that the collection of functions creates a program. The function is also known as procedure or subroutine in other programming languages.

Advantage of functions in C

There are the following advantages of C functions.

• By using functions, we can avoid rewriting same logic/code again and again in a program.
• We can call C functions any number of times in a program and from any place in a program.
• We can track a large C program easily when it is divided into multiple functions.
• Reusability is the main achievement of C functions.
• However, Function calling is always an overhead in a C program.

Function Aspects

There are three aspects of a C function.

• Function declaration A function must be declared globally in a c program to tell the compiler about the function name, function parameters, and return type.

• Function call Function can be called from anywhere in the program. The parameter list must not differ in function calling and function declaration. We must pass the same number of functions as it is declared in the function declaration.

• Function definition It contains the actual statements which are to be executed. It is the most important aspect to which the control comes when the function is called. Here, we must notice that only one value can be returned from the function.

The syntax of creating function in c language is given below:

1. Return_type function_name(data_type parameter...){  
2. //code to be executed  
3. }  

Types of Functions

There are two types of functions in C programming:

1. Library Functions: are the functions which are declared in the C header files such as scanf(), printf(), gets(), puts(), ceil(), floor() etc.
2. User-defined functions: are the functions which are created by the C programmer, so that he/she can use it many times. It reduces the complexity of a big program and optimizes the code.

Return Value

A C function may or may not return a value from the function. If you don't have to return any value from the function, use void for the return type.

Let's see a simple example of C function that doesn't return any value from the function.

Example without return value:

1. Void hello(){  
2. Printf("hello c");  
3. }  

If you want to return any value from the function, you need to use any data type such as int, long, char, etc. The return type depends on the value to be returned from the function.

Let's see a simple example of C function that returns int value from the function.

Example with return value:

1. Int get(){  
2. Return 10;  
3. }  

In the above example, we have to return 10 as a value, so the return type is int. If you want to return floating-point value (e.g., 10.2, 3.1, 54.5, etc), you need to use float as the return type of the method.

1. Float get(){  
2. Return 10.2;  
3. }  

Now, you need to call the function, to get the value of the function.

Different aspects of function calling

A function may or may not accept any argument. It may or may not return any value. Based on these facts, there are four different aspects of function calls.

• Function without arguments and without return value
• Function without arguments and with return value
• Function with arguments and without return value
• Function with arguments and with return value

Example for Function without argument and return value

Example 1

1. #include<stdio.h>  
2. Void printName();  
3. Void main ()  
4. {  
5.    Printf("Hello ");  
6.    PrintName();  
7. }  
8. Void printName()  
9. {  
10.    Printf("Javatpoint");  
11. }  

Output

Hello Javatpoint

Example 2

1. #include<stdio.h>  
2. Void sum();  
3. Void main()  
4. {  
5.    Printf("\nGoing to calculate the sum of two numbers:");  
6.    Sum();  
7. }  
8. Void sum()  
9. {  
10.    Int a,b;   
11.    Printf("\nEnter two numbers");  
12.    Scanf("%d %d",&a,&b);   
13.    Printf("The sum is %d",a+b);  
14. }  

Output

Going to calculate the sum of two numbers:

Enter two numbers 10

24

The sum is 34

Example for Function without argument and with return value

Example 1

1. #include<stdio.h>  
2. Int sum();  
3. Void main()  
4. {  
5.    Int result;   
6.    Printf("\nGoing to calculate the sum of two numbers:");  
7.    Result = sum();  
8.    Printf("%d",result);  
9. }  
10. Int sum()  
11. {  
12.    Int a,b;   
13.    Printf("\nEnter two numbers");  
14.    Scanf("%d %d",&a,&b);  
15.    Return a+b;   
16. }  

Output

Going to calculate the sum of two numbers:

Enter two numbers 10

24

The sum is 34

Example 2: program to calculate the area of the square

1. #include<stdio.h>  
2. Int sum();  
3. Void main()  
4. {  
5.    Printf("Going to calculate the area of the square\n");  
6.    Float area = square();  
7.    Printf("The area of the square: %f\n",area);  
8. }  
9. Int square()  
10. {  
11.    Float side;  
12.    Printf("Enter the length of the side in meters: ");  
13.    Scanf("%f",&side);  
14.    Return side * side;  
15. }  

Output

Going to calculate the area of the square

Enter the length of the side in meters: 10

The area of the square: 100.000000

Example for Function with argument and without return value

Example 1

1. #include<stdio.h>  
2. Void sum(int, int);  
3. Void main()  
4. {  
5.    Int a,b,result;   
6.    Printf("\nGoing to calculate the sum of two numbers:");  
7.    Printf("\nEnter two numbers:");  
8.    Scanf("%d %d",&a,&b);  
9.    Sum(a,b);  
10. }  
11. Void sum(int a, int b)  
12. {  
13.    Printf("\nThe sum is %d",a+b);      
14. }  

Output

Going to calculate the sum of two numbers:

Enter two numbers 10

24

The sum is 34

Example 2: program to calculate the average of five numbers.

1. #include<stdio.h>  
2. Void average(int, int, int, int, int);  
3. Void main()  
4. {  
5.    Int a,b,c,d,e;   
6.    Printf("\nGoing to calculate the average of five numbers:");  
7.    Printf("\nEnter five numbers:");  
8.    Scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);  
9.    Average(a,b,c,d,e);  
10. }  
11. Void average(int a, int b, int c, int d, int e)  
12. {  
13.    Float avg;   
14.    Avg = (a+b+c+d+e)/5;   
15.    Printf("The average of given five numbers : %f",avg);  
16. }  

Output

Going to calculate the average of five numbers:

Enter five numbers:10

20

30

40

50

The average of given five numbers : 30.000000

Example for Function with argument and with return value

Example 1

1. #include<stdio.h>  
2. Int sum(int, int);  
3. Void main()  
4. {  
5.    Int a,b,result;   
6.    Printf("\nGoing to calculate the sum of two numbers:");  
7.    Printf("\nEnter two numbers:");  
8.    Scanf("%d %d",&a,&b);  
9.    Result = sum(a,b);  
10.    Printf("\nThe sum is : %d",result);  
11. }  
12. Int sum(int a, int b)  
13. {  
14.    Return a+b;  
15. }  

Output

Going to calculate the sum of two numbers:

Enter two numbers:10

20

The sum is : 30  

Example 2: Program to check whether a number is even or odd

1. #include<stdio.h>  
2. Int even_odd(int);  
3. Void main()  
4. {  
5. Int n,flag=0;  
6. Printf("\nGoing to check whether a number is even or odd");  
7. Printf("\nEnter the number: ");  
8. Scanf("%d",&n);  
9. Flag = even_odd(n);  
10. If(flag == 0)  
11. {  
12.    Printf("\nThe number is odd");  
13. }  
14. Else   
15. {  
16.    Printf("\nThe number is even");  
17. }  
18. }  
19. Int even_odd(int n)  
20. {  
21.    If(n%2 == 0)  
22.    {  
23.        Return 1;  
24.    }  
25.    Else   
26.    {  
27.        Return 0;  
28.    }  
29. }  

Output

Going to check whether a number is even or odd

Enter the number: 100

The number is even

C Library Functions

Library functions are the inbuilt function in C that are grouped and placed at a common place called the library. Such functions are used to perform some specific operations. For example, printf is a library function used to print on the console. The library functions are created by the designers of compilers. All C standard library functions are defined inside the different header files saved with the extension .h. We need to include these header files in our program to make use of the library functions defined in such header files. For example, to use the library functions such as printf/scanf we need to include stdio.h in our program which is a header file that contains all the library functions regarding standard input/output.

The list of mostly used header files is given in the following table.

2.5 Passing the parameters

Call by value and Call by reference in C

There are two methods to pass the data into the function in C language, i.e., call by value and call by reference.

Let's understand call by value and call by reference in c language one by one.

Call by value in C

• In call by value method, the value of the actual parameters is copied into the formal parameters. In other words, we can say that the value of the variable is used in the function call in the call by value method.
• In call by value method, we cannot modify the value of the actual parameter by the formal parameter.
• In call by value, different memory is allocated for actual and formal parameters since the value of the actual parameter is copied into the formal parameter.
• The actual parameter is the argument which is used in the function call whereas formal parameter is the argument which is used in the function definition.

Let's try to understand the concept of call by value in c language by the example given below:

1. #include<stdio.h>  
2. Void change(int num) {    
3.    Printf("Before adding value inside function num=%d \n",num);    
4.    Num=num+100;    
5.    Printf("After adding value inside function num=%d \n", num);    
6. }    
7. Int main() {    
8.    Int x=100;    
9.    Printf("Before function call x=%d \n", x);    
10.    Change(x);//passing value in function    
11.    Printf("After function call x=%d \n", x);    
12. Return 0;  
13. }    

Output

Before function call x=100

Before adding value inside function num=100

After adding value inside function num=200

After function call x=100

Call by Value Example: Swapping the values of the two variables

1. #include <stdio.h>  
2. Void swap(int , int); //prototype of the function   
3. Int main()  
4. {  
5.    Int a = 10;  
6.    Int b = 20;   
7.    Printf("Before swapping the values in main a = %d, b = %d\n",a,b); // printing the value of a and b in main  
8.    Swap(a,b);  
9.    Printf("After swapping values in main a = %d, b = %d\n",a,b); // The value of actual parameters do not change by changing the formal parameters in call by value, a = 10, b = 20  
10. }  
11. Void swap (int a, int b)  
12. {  
13.    Int temp;   
14.    Temp = a;  
15.    a=b;  
16.    b=temp;  
17.    Printf("After swapping values in function a = %d, b = %d\n",a,b); // Formal parameters, a = 20, b = 10   
18. }  

Output

Before swapping the values in main a = 10, b = 20

After swapping values in function a = 20, b = 10

After swapping values in main a = 10, b = 20 

Call by reference in C

• In call by reference, the address of the variable is passed into the function call as the actual parameter.
• The value of the actual parameters can be modified by changing the formal parameters since the address of the actual parameters is passed.
• In call by reference, the memory allocation is similar for both formal parameters and actual parameters. All the operations in the function are performed on the value stored at the address of the actual parameters, and the modified value gets stored at the same address.

Consider the following example for the call by reference.

1. #include<stdio.h>  
2. Void change(int *num) {    
3.    Printf("Before adding value inside function num=%d \n",*num);    
4.    (*num) += 100;    
5.    Printf("After adding value inside function num=%d \n", *num);    
6. }      
7. Int main() {    
8.    Int x=100;    
9.    Printf("Before function call x=%d \n", x);    
10.    Change(&x);//passing reference in function    
11.    Printf("After function call x=%d \n", x);    
12. Return 0;  
13. }    

Output

Before function call x=100

Before adding value inside function num=100

After adding value inside function num=200

After function call x=200

Call by reference Example: Swapping the values of the two variables

1. #include <stdio.h>  
2. Void swap(int *, int *); //prototype of the function   
3. Int main()  
4. {  
5.    Int a = 10;  
6.    Int b = 20;   
7.    Printf("Before swapping the values in main a = %d, b = %d\n",a,b); // printing the value of a and b in main  
8.    Swap(&a,&b);  
9.    Printf("After swapping values in main a = %d, b = %d\n",a,b); // The values of actual parameters do change in call by reference, a = 10, b = 20  
10. }  
11. Void swap (int *a, int *b)  
12. {  
13.    Int temp;   
14.    Temp = *a;  
15.    *a=*b;  
16.    *b=temp;  
17.    Printf("After swapping values in function a = %d, b = %d\n",*a,*b); // Formal parameters, a = 20, b = 10   
18. }  

Output

Before swapping the values in main a = 10, b = 20

After swapping values in function a = 20, b = 10

After swapping values in main a = 20, b = 10 

Difference between call by value and call by reference in c

2.6 Automatic variables

The variables which are declared inside a block are known as automatic or local variables; these variables allocates memory automatically upon entry to that block and free the occupied memory upon exit from that block.

These variables have local scope to that block only that means these can be accessed in which variable declared.

Keyword 'auto' may be used to declare automatic variable but we can declare these variable without using 'auto' keywords.

Consider the following declarations

Int main()

{

Auto int a;

Int b;

....

Return 0;

}

Here, both variables a and b are automatic variables.

Automatic variables in other user defined functions

An automatic or local variable can be declared in any user define function in the starting of the block.

Consider the following code

Void myFunction(void)

{

Int x;

Float y;

Char z;

...

}

Int main()

{

Int a,b;

MyFunction();

....

Return 0;

}

In this code snippet, variables x, y and z are the local/automatic variable of myFunction() function, while variables a and b are the local/automatic variables of main() function.

2.7 Scope and extent of variables

A scope in any programming is a region of the program where a defined variable can have its existence and beyond that variable it cannot be accessed. There are three places where variables can be declared in C programming language −

• Inside a function or a block which is called local variables.
• Outside of all functions which is called global variables.
• In the definition of function parameters which are called formal parameters.

Let us understand what are local and global variables, and formal parameters.

Local Variables

Variables that are declared inside a function or block are called local variables. They can be used only by statements that are inside that function or block of code. Local variables are not known to functions outside their own. The following example shows how local variables are used. Here all the variables a, b, and c are local to main() function.

#include <stdio.h>

Int main () {

/* local variable declaration */

Int a, b;

Int c;

/* actual initialization */

a = 10;

b = 20;

c = a + b;

Printf ("value of a = %d, b = %d and c = %d\n", a, b, c);

Return 0;

}

Global Variables

Global variables are defined outside a function, usually on top of the program. Global variables hold their values throughout the lifetime of your program and they can be accessed inside any of the functions defined for the program.

A global variable can be accessed by any function. That is, a global variable is available for use throughout your entire program after its declaration. The following program show how global variables are used in a program.

#include <stdio.h>

/* global variable declaration */

Int g;

Int main () {

/* local variable declaration */

Int a, b;

/* actual initialization */

a = 10;

b = 20;

g = a + b;

Printf ("value of a = %d, b = %d and g = %d\n", a, b, g);

Return 0;

}

A program can have same name for local and global variables but the value of local variable inside a function will take preference. Here is an example −

#include <stdio.h>

/* global variable declaration */

Int g = 20;

Int main () {

/* local variable declaration */

Int g = 10;

Printf ("value of g = %d\n",  g);

Return 0;

}

When the above code is compiled and executed, it produces the following result −

Value of g = 10

Formal Parameters

Formal parameters, are treated as local variables with-in a function and they take precedence over global variables. Following is an example −

#include <stdio.h>

/* global variable declaration */

Int a = 20;

Int main () {

/* local variable declaration in main function */

Int a = 10;

Int b = 20;

Int c = 0;

Printf ("value of a in main() = %d\n",  a);

c = sum( a, b);

Printf ("value of c in main() = %d\n",  c);

Return 0;

}

/* function to add two integers */

Int sum(int a, int b) {

Printf ("value of a in sum() = %d\n",  a);

Printf ("value of b in sum() = %d\n",  b);

Return a + b;

}

When the above code is compiled and executed, it produces the following result −

Value of a in main() = 10

Value of a in sum() = 10

Value of b in sum() = 20

Value of c in main() = 30

Initializing Local and Global Variables

When a local variable is defined, it is not initialized by the system, you must initialize it yourself. Global variables are initialized automatically by the system when you define them as follows −

It is a good programming practice to initialize variables properly, otherwise your program may produce unexpected results, because uninitialized variables will take some garbage value already available at their memory location.

2.8 Storage classes

Storage classes in C are used to determine the lifetime, visibility, memory location, and initial value of a variable. There are four types of storage classes in C

• Automatic
• External
• Static
• Register

Automatic

• Automatic variables are allocated memory automatically at runtime.
• The visibility of the automatic variables is limited to the block in which they are defined.

The scope of the automatic variables is limited to the block in which they are defined.

• The automatic variables are initialized to garbage by default.
• The memory assigned to automatic variables gets freed upon exiting from the block.
• The keyword used for defining automatic variables is auto.
• Every local variable is automatic in C by default.

Example 1

1. #include <stdio.h>  
2. Int main()  
3. {  
4. Int a; //auto  
5. Char b;  
6. Float c;   
7. Printf("%d %c %f",a,b,c); // printing initial default value of automatic variables a, b, and c.   
8. Return 0;  
9. }  

Output:

Garbage garbage garbage

Example 2

1. #include <stdio.h>  
2. Int main()  
3. {  
4. Int a = 10,i;   
5. Printf("%d ",++a);  
6. {  
7. Int a = 20;   
8. For (i=0;i<3;i++)  
9. {  
10. Printf("%d ",a); // 20 will be printed 3 times since it is the local value of a  
11. }  
12. }  
13. Printf("%d ",a); // 11 will be printed since the scope of a = 20 is ended.   
14. }  

Output:

11 20 20 20 11

Static

• The variables defined as static specifier can hold their value between the multiple function calls.
• Static local variables are visible only to the function or the block in which they are defined.
• A same static variable can be declared many times but can be assigned at only one time.
• Default initial value of the static integral variable is 0 otherwise null.
• The visibility of the static global variable is limited to the file in which it has declared.
• The keyword used to define static variable is static.

Example 1

1. #include<stdio.h>  
2. Static char c;  
3. Static int i;  
4. Static float f;   
5. Static char s[100];  
6. Void main ()  
7. {  
8. Printf("%d %d %f %s",c,i,f); // the initial default value of c, i, and f will be printed.   
9. }  

Output:

0 0 0.000000 (null)

Example 2

1. #include<stdio.h>  
2. Void sum()  
3. {  
4. Static int a = 10;  
5. Static int b = 24;   
6. Printf("%d %d \n",a,b);  
7. a++;   
8. b++;  
9. }  
10. Void main()  
11. {  
12. Int i;  
13. For(i = 0; i< 3; i++)  
14. {  
15. Sum(); // The static variables holds their value between multiple function calls.    
16. }  
17. }  

Output:

10 24

11 25

12 26

Register

• The variables defined as the register is allocated the memory into the CPU registers depending upon the size of the memory remaining in the CPU.
• We cannot dereference the register variables, i.e., we cannot use &operator for the register variable.
• The access time of the register variables is faster than the automatic variables.
• The initial default value of the register local variables is 0.
• The register keyword is used for the variable which should be stored in the CPU register. However, it is compilers choice whether or not; the variables can be stored in the register.
• We can store pointers into the register, i.e., a register can store the address of a variable.
• Static variables cannot be stored into the register since we cannot use more than one storage specifier for the same variable.

Example 1

1. #include <stdio.h>  
2. Int main()  
3. {  
4. Register int a; // variable a is allocated memory in the CPU register. The initial default value of a is 0.   
5. Printf("%d",a);  
6. }  

Output:

0

Example 2

1. #include <stdio.h>  
2. Int main()  
3. {  
4. Register int a = 0;   
5. Printf("%u",&a); // This will give a compile time error since we can not access the address of a register variable.   
6. }  

Output:

Main.c:5:5: error: address of register variable ?a? requested

Printf("%u",&a);

^~~~~~

External

• The external storage class is used to tell the compiler that the variable defined as extern is declared with an external linkage elsewhere in the program.
• The variables declared as extern are not allocated any memory. It is only declaration and intended to specify that the variable is declared elsewhere in the program.
• The default initial value of external integral type is 0 otherwise null.
• We can only initialize the extern variable globally, i.e., we cannot initialize the external variable within any block or method.
• An external variable can be declared many times but can be initialized at only once.
• If a variable is declared as external then the compiler searches for that variable to be initialized somewhere in the program which may be extern or static. If it is not, then the compiler will show an error.

Example 1

1. #include <stdio.h>  
2. Int main()  
3. {  
4. Extern int a;   
5. Printf("%d",a);  
6. }  

Output

Main.c:(.text+0x6): undefined reference to a'

Collect2: error: ld returned 1 exit status

Example 2

1. #include <stdio.h>  
2. Int a;   
3. Int main()  
4. {  
5. Extern int a; // variable a is defined globally, the memory will not be allocated to a  
6. Printf("%d",a);  
7. }  

Output

0

Example 3

1. #include <stdio.h>  
2. Int a;   
3. Int main()  
4. {  
5. Extern int a = 0; // this will show a compiler error since we can not use extern and initializer at same time   
6. Printf("%d",a);  
7. }  

Output

Compile time error

Main.c: In function ?main?:

Main.c:5:16: error: ?a? has both ?extern? and initializer

Extern int a = 0;

Example 4

1. #include <stdio.h>  
2. Int main()  
3. {  
4. Extern int a; // Compiler will search here for a variable a defined and initialized somewhere in the pogram or not.   
5. Printf("%d",a);  
6. }  
7. Int a = 20;  

Output

20

Example 5

1. Extern int a;  
2. Int a = 10;   
3. #include <stdio.h>  
4. Int main()  
5. {  
6. Printf("%d",a);  
7. }  
8. Int a = 20; // compiler will show an error at this line   

Output

Compile time error

2.9 Recursion

Recursion is the process which comes into existence when a function calls a copy of itself to work on a smaller problem. Any function which calls itself is called recursive function, and such function calls are called recursive calls. Recursion involves several numbers of recursive calls. However, it is important to impose a termination condition of recursion. Recursion code is shorter than iterative code however it is difficult to understand.

Recursion cannot be applied to all the problem, but it is more useful for the tasks that can be defined in terms of similar subtasks. For Example, recursion may be applied to sorting, searching, and traversal problems.

Generally, iterative solutions are more efficient than recursion since function call is always overhead. Any problem that can be solved recursively, can also be solved iteratively. However, some problems are best suited to be solved by the recursion, for example, tower of Hanoi, Fibonacci series, factorial finding, etc.

In the following example, recursion is used to calculate the factorial of a number.

1. #include <stdio.h>  
2. Int fact (int);  
3. Int main()  
4. {  
5.    Int n,f;  
6.    Printf("Enter the number whose factorial you want to calculate?");  
7.    Scanf("%d",&n);  
8.    f = fact(n);  
9.    Printf("factorial = %d",f);  
10. }  
11. Int fact(int n)  
12. {  
13.    If (n==0)  
14.    {  
15.        Return 0;  
16.    }  
17.    Else if ( n == 1)  
18.    {  
19.        Return 1;  
20.    }  
21.    Else   
22.    {  
23.        Return n*fact(n-1);  
24.    }  
25. }  

Output

Enter the number whose factorial you want to calculate?5

Factorial = 120

We can understand the above program of the recursive method call by the figure given below:

Recursive Function

A recursive function performs the tasks by dividing it into the subtasks. There is a termination condition defined in the function which is satisfied by some specific subtask. After this, the recursion stops and the final result is returned from the function.

The case at which the function doesn't recur is called the base case whereas the instances where the function keeps calling itself to perform a subtask, is called the recursive case. All the recursive functions can be written using this format.

Pseudocode for writing any recursive function is given below.

1. If (test_for_base)  
2. {  
3.    Return some_value;  
4. }  
5. Else if (test_for_another_base)  
6. {  
7.    Return some_another_value;  
8. }  
9. Else  
10. {  
11.    // Statements;  
12.    Recursive call;  
13. }  

Example of recursion in C

Let's see an example to find the nth term of the Fibonacci series.

1. #include<stdio.h>  
2. Int fibonacci(int);  
3. Void main ()  
4. {  
5.    Int n,f;  
6.    Printf("Enter the value of n?");  
7.    Scanf("%d",&n);  
8.    f = fibonacci(n);  
9.    Printf("%d",f);  
10. }  
11. Int fibonacci (int n)  
12. {  
13.    If (n==0)  
14.    {  
15.    Return 0;  
16.    }  
17.    Else if (n == 1)  
18.    {  
19.        Return 1;   
20.    }  
21.    Else  
22.    {  
23.        Return fibonacci(n-1)+fibonacci(n-2);  
24.    }  
25. }  

Output

Enter the value of n?12

144

Memory allocation of Recursive method

Each recursive call creates a new copy of that method in the memory. Once some data is returned by the method, the copy is removed from the memory. Since all the variables and other stuff declared inside function get stored in the stack, therefore a separate stack is maintained at each recursive call. Once the value is returned from the corresponding function, the stack gets destroyed. Recursion involves so much complexity in resolving and tracking the values at each recursive call. Therefore, we need to maintain the stack and track the values of the variables defined in the stack.

Let us consider the following example to understand the memory allocation of the recursive functions.

1. Int display (int n)  
2. {  
3.    If(n == 0)  
4.        Return 0; // terminating condition  
5.    Else   
6.    {  
7.        Printf("%d",n);  
8.        Return display(n-1); // recursive call  
9.    }  
10. }  

Explanation

Let us examine this recursive function for n = 4. First, all the stacks are maintained which prints the corresponding value of n until n becomes 0, Once the termination condition is reached, the stacks get destroyed one by one by returning 0 to its calling stack. Consider the following image for more information regarding the stack trace for the recursive functions.

2.10 Iteration vs Recursion

The Recursion and Iteration both repeatedly execute the set of instructions. Recursion is when a statement in a function calls itself repeatedly. The iteration is when a loop repeatedly executes until the controlling condition becomes false. The primary difference between recursion and iteration is that recursion is a process, always applied to a function and iteration is applied to the set of instructions which we want to get repeatedly executed.

Recursion

• Recursion uses selection structure.
• Infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on some condition (base case) and Infinite recursion can crash the system.
• Recursion terminates when a base case is recognized.
• Recursion is usually slower than iteration due to the overhead of maintaining the stack.
• Recursion uses more memory than iteration.
• Recursion makes the code smaller.

Example

Public class RecursionExample {

Public static void main(String args[]) {

RecursionExample re = new RecursionExample();

Int result = re.factorial(4);

System.out.println("Result:" + result);

}

Public int factorial(int n) {

If (n==0) {

Return 1;

}

Else {

Return n*factorial(n-1);

}

}

}

Output

Result:24

Iteration

• Iteration uses repetition structure.
• An infinite loop occurs with iteration if the loop condition test never becomes false and Infinite looping uses CPU cycles repeatedly.
• An iteration terminates when the loop condition fails.
• An iteration does not use the stack so it's faster than recursion.
• Iteration consumes less memory.
• Iteration makes the code longer.

Example

Public class IterationExample {

Public static void main(String args[]) {

For(int i = 1; i <= 5; i++) {

System.out.println(i + " ");

}

}

}

Output

1

2

3

4

5

2.11 Types of recursion

What is Recursion?
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.

Types of Recursions:
Recursion are mainly of two types depending on whether a function calls itself from within itself or more than one function call one another mutually. The first one is called direct recursion and another one is called indirect recursion. Thus, the two types of recursion are:

1. Direct Recursion: These can be further categorized into four types:
   • Tail Recursion: If a recursive function calling itself and that recursive call is the last statement in the function then it’s known as Tail Recursion.After that call the recursive function performs nothing. The function has to process or perform any operation at the time of calling and it does nothing at returning time.

Example:

Output:

3 2 1

Let’s understand the example by tracing tree of recursive function. That is how the calls are made and how the outputs are produced.

Time Complexity for Tail Recursion : O(n)
Space Complexity for Tail Recursion : O(n)

Note: Time & Space Complexity is given for this specific example. It may vary for another example.

Lets’ now converting Tail Recursion into Loop and compare each other in terms of Time & Space Complexity and decide which is more efficient.

Output:

3 2 1

Time Complexity: O(n)
Space Complexity: O(1)

Note: Time & Space Complexity is given for this specific example. It may vary for another example.

So, it was seen that in case of loop the Space Complexity is O(1) so it was better to write code in loop instead of tail recursion in terms of Space Complexity which is more efficient than tail recursion.

Why space complexity is less in case of loop ?

Before explaining this I am assuming that you are familiar with the knowledge that’s how the data stored in main memory during execution of a program. In brief, when the program executes, the main memory divided into three parts. One part for code section, second one is heap memory and another one is stack memory. Remember that the program can directly access only the stack memory , it can’t directly access the heap memory so we need the help of pointer to access the heap memory.

Let’s now understand why space complexity is less in case of loop ?

In case of loop when function “(void fun(int y))” executes there only one activation record created in stack memory(activation record created for only ‘y’ variable) so it takes only ‘one’ unit of memory inside stack so its space complexity is O(1) but in case of recursive function every time it calls itself for each call a separate activation record created in stack. So, if there’s ‘n’ no of call then it takes ‘n’ unit of memory inside stack so its space complexity is O(n).

• Head Recursion: If a recursive function calling itself and that recursive call is the first statement in the function then it’s known as Head Recursion.There’s no statement, no operation before the call. The function doesn’t have to process or perform any operation at the time of calling and all operations are done at returning time.

Example:

Output:

1 2 3

Let’s understand the example by tracing tree of recursive function. That is how the calls are made and how the outputs are produced.

Time Complexity for Head Recursion: O(n)
Space Complexity for Head Recursion: O(n)

Note: Time & Space Complexity is given for this specific example. It may vary for another example.

Note: Head recursion can’t easily convert into loop as Tail Recursion but it can.Let’s convert the above code into the loop.

Output:

1 2 3

• Tree Recursion: To understand Tree Recursion let’s first understand Linear Recursion. If a recursive function calling itself for one time then it’s known as Linear Recursion. Otherwise if a recursive function calling itself for more than one time then it’s known as Tree Recursion.

Example:

Pseudo Code for linear recursion

Fun(n)

{

If(n>0)

{

// some code

Fun(n-1); // Calling itself only once

{

//some code

}

Program for tree recursion

Output:

3 2 1 1 2 1 1

Let’s understand the example by tracing tree of recursive function. That is how the calls are made and how the outputs are produced.

Time Complexity for Tree Recursion: O(2^n)
Space Complexity for Tree Recursion: O(n)

Note: Time & Space Complexity is given for this specific example. It may vary for another example.

• Nested Recursion: In this recursion, a recursive function will pass the parameter as a recursive call. That means “recursion inside recursion”. Let see the example to understand this recursion.

Example:

Output:

91

Let’s understand the example by tracing tree of recursive function. That is how the calls are made and how the outputs are produced.

2.     Indirect Recursion: In this recursion, there may be more than one functions and they are calling one another in a circular manner.

From the above diagram fun(A) is calling for fun(B), fun(B) is calling for fun(C) and fun(C) is calling for fun(A) and thus it makes a cycle.

Example:

Output:

20 19 9 8 4 3 1

Let’s understand the example by tracing tree of recursive function. That is how the calls are made and how the outputs are produced.

2.12 Simple recursive and non-recursive programs

Example: Sum of Natural Numbers Using Recursion

#include <stdio.h>

Int sum(int n);

Int main() {

Int number, result;

Printf("Enter a positive integer: ");

Scanf("%d", &number);

Result = sum(number);

Printf("sum = %d", result);

Return 0;

}

Int sum(int n) {

If (n != 0)

// sum() function calls itself

Return n + sum(n-1);

Else

Return n;

}

Output

Enter a positive integer:3

Sum = 6

Factorial of a Number Using Recursion

#include<stdio.h>

Long int multiplyNumbers(int n);

Int main() {

Int n;

Printf("Enter a positive integer: ");

Scanf("%d",&n);

Printf("Factorial of %d = %ld", n, multiplyNumbers(n));

Return 0;

}

Long int multiplyNumbers(int n) {

If (n>=1)

Return n*multiplyNumbers(n-1);

Else

Return 1;

}

Output

Enter a positive integer: 6

Factorial of 6 = 720

Suppose the user entered 6.

Initially, multiplyNumbers() is called from main() with 6 passed as an argument.

Then, 5 is passed to multiplyNumbers() from the same function (recursive call). In each recursive call, the value of argument n is decreased by 1.

When the value of n is less than 1, there is no recursive call and the factorial is returned ultimately to the main() function.

Factorial of a number is nothing but the multiplication of numbers from a given number to 1 Ex: 5! =5*4*3*2*1= 120

#include <stdio.h>

#include <conio.h>

Void main()

{

Int n, a, b;

Clrscr();

Printf("Enter any number\n");

Scanf("%d", &n);

a = recfactorial(n);

Printf("The factorial of a given number using recursion is %d \n", a);

b = nonrecfactorial(n);

Printf("The factorial of a given number using nonrecursion is %d ", b);

Getch();

}

Int recfactorial(int x)

{

Int f;

If(x == 0)

{

Return(1);

}

Else

{

f = x * recfactorial(x - 1);

Return(f);

}

}

Int nonrecfactorial(int x)

{

Int i, f = 1;

For(i = 1;i <= x; i++)

{

f = f * i;

}

Return(f);

}

Input & Output:

Enter any number

5

The factorial of a given number using recursion is 120

The factorial of a given number using nonrecursion is 1

2.13 Towers of Hanoi problem

The tower of Hanoi is a mathematical puzzle. It consists of three rods and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top. We have to obtain the same stack on the third rod.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules−

• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
• No disk may be placed on top of a smaller disk.

Sample

Input  − 3

Output   − A to B 

A to C 

B to C 

A to B 

C to A 

C to B 

A to B  Explanation − uses recursive function & solves the tower of Hanoi.

Example

#include<stdio.h>

Void TOH(int n,char x,char y,char z) {

If(n>0) {

TOH(n-1,x,z,y);

Printf("\n%c to %c",x,y);

TOH(n-1,z,y,x);

}

}

Int main() {

Int n=3;

TOH(n,'A','B','C');

}

Output

A to B

A to C

B to C

A to B

C to A

C to B

A to B

Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted −

These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same.

Rules

The mission is to move all the disks to some another tower without violating the sequence of arrangement. A few rules to be followed for Tower of Hanoi are −

• Only one disk can be moved among the towers at any given time.
• Only the "top" disk can be removed.
• No large disk can sit over a small disk.

Following is an animated representation of solving a Tower of Hanoi puzzle with three disks.

Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.

Algorithm

To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with lesser number of disks, say → 1 or 2. We mark three towers with name, source, destination and aux (only to help moving the disks). If we have only one disk, then it can easily be moved from source to destination peg.

If we have 2 disks −

• First, we move the smaller (top) disk to aux peg.
• Then, we move the larger (bottom) disk to destination peg.
• And finally, we move the smaller disk from aux to destination peg.

So now, we are in a position to design an algorithm for Tower of Hanoi with more than two disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part.

Our ultimate aim is to move disk n from source to destination and then put all other (n1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks.

The steps to follow are −

Step 1 − Move n-1 disks from source to aux

Step 2 − Move nth disk from source to dest

Step 3 − Move n-1 disks from aux to dest

A recursive algorithm for Tower of Hanoi can be driven as follows −

START

Procedure Hanoi(disk, source, dest, aux)

IF disk == 1, THEN

Move disk from source to dest            

ELSE

Hanoi(disk - 1, source, aux, dest)     // Step 1

Move disk from source to dest          // Step 2

Hanoi(disk - 1, aux, dest, source)     // Step 3

END IF

END Procedure

STOP

Tower of Hanoi

Program

#include <stdio.h>

#include <stdbool.h>

#define MAX 10

Int list[MAX] = {1,8,4,6,0,3,5,2,7,9};

Void display(){

Int i;

Printf("[");

// navigate through all items

For(i = 0; i < MAX; i++) {

Printf("%d ",list[i]);

}

Printf("]\n");

}

Void bubbleSort() {

Int temp;

Int i,j;

Bool swapped = false;      

// loop through all numbers

For(i = 0; i < MAX-1; i++) {

Swapped = false;

// loop through numbers falling ahead

For(j = 0; j < MAX-1-i; j++) {

Printf("Items compared: [ %d, %d ] ", list[j],list[j+1]);

// check if next number is lesser than current no

//   swap the numbers.

//  (Bubble up the highest number)

If(list[j] > list[j+1]) {

Temp = list[j];

List[j] = list[j+1];

List[j+1] = temp;

Swapped = true;

Printf(" => swapped [%d, %d]\n",list[j],list[j+1]);

} else {

Printf(" => not swapped\n");

}

}

// if no number was swapped that means

//   array is sorted now, break the loop.

If(!swapped) {

Break;

}

Printf("Iteration %d#: ",(i+1));

Display();                    

}   

}

Int main() {

Printf("Input Array: ");

Display();

Printf("\n");

BubbleSort();

Printf("\nOutput Array: ");

Display();

}

If we compile and run the above program, it will produce the following result −

Output

Input Array: [1 8 4 6 0 3 5 2 7 9 ]

Items compared: [ 1, 8 ]  => not swapped

Items compared: [ 8, 4 ]  => swapped [4, 8]

Items compared: [ 8, 6 ]  => swapped [6, 8]

Items compared: [ 8, 0 ]  => swapped [0, 8]

Items compared: [ 8, 3 ]  => swapped [3, 8]

Items compared: [ 8, 5 ]  => swapped [5, 8]

Items compared: [ 8, 2 ]  => swapped [2, 8]

Items compared: [ 8, 7 ]  => swapped [7, 8]

Items compared: [ 8, 9 ]  => not swapped

Iteration 1#: [1 4 6 0 3 5 2 7 8 9 ]

Items compared: [ 1, 4 ]  => not swapped

Items compared: [ 4, 6 ]  => not swapped

Items compared: [ 6, 0 ]  => swapped [0, 6]

Items compared: [ 6, 3 ]  => swapped [3, 6]

Items compared: [ 6, 5 ]  => swapped [5, 6]

Items compared: [ 6, 2 ]  => swapped [2, 6]

Items compared: [ 6, 7 ]  => not swapped

Items compared: [ 7, 8 ]  => not swapped

Iteration 2#: [1 4 0 3 5 2 6 7 8 9 ]

Items compared: [ 1, 4 ]  => not swapped

Items compared: [ 4, 0 ]  => swapped [0, 4]

Items compared: [ 4, 3 ]  => swapped [3, 4]

Items compared: [ 4, 5 ]  => not swapped

Items compared: [ 5, 2 ]  => swapped [2, 5]

Items compared: [ 5, 6 ]  => not swapped

Items compared: [ 6, 7 ]  => not swapped

Iteration 3#: [1 0 3 4 2 5 6 7 8 9 ]

Items compared: [ 1, 0 ]  => swapped [0, 1]

Items compared: [ 1, 3 ]  => not swapped

Items compared: [ 3, 4 ]  => not swapped

Items compared: [ 4, 2 ]  => swapped [2, 4]

Items compared: [ 4, 5 ]  => not swapped

Items compared: [ 5, 6 ]  => not swapped

Iteration 4#: [0 1 3 2 4 5 6 7 8 9 ]

Items compared: [ 0, 1 ]  => not swapped

Items compared: [ 1, 3 ]  => not swapped

Items compared: [ 3, 2 ]  => swapped [2, 3]

Items compared: [ 3, 4 ]  => not swapped

Items compared: [ 4, 5 ]  => not swapped

Iteration 5#: [0 1 2 3 4 5 6 7 8 9 ]

Items compared: [ 0, 1 ]  => not swapped

Items compared: [ 1, 2 ]  => not swapped

Items compared: [ 2, 3 ]  => not swapped

Items compared: [ 3, 4 ]  => not swapped

Output Array: [0 1 2 3 4 5 6 7 8 9 ]

Text Books:

1. Programming with C-Gottfried-Schaums Outline Series-TMH

2. C Programming – Anitha Goel/Ajay Mittal/E.Sreenivasa Reddy-Pearson India

References:

1. Problem Solving with C- Somasekharan-PHI.

2. C Programming- Behrouz A forouzan – CENGAGE Learning

3. Test your c skills-Yaswanth kanithker

4. Let us C- Yaswanth kanithker