UNIT 4

UNIT 4

Function

1. What are functions explain in detail with examples?

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 procedureor subroutinein 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 a 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

2.     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

3.     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

4.     What is 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.

5.     Explain Recursion with examples

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

6.     Explain 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.

A function that calls itself is known as a recursive function. And, this technique is known as recursion.

How recursion works?

Void recurse()

{

    ... .. ...

    recurse();

    ... .. ...

}

Int main()

{

    ... .. ...

    recurse();

    ... .. ...

}

The recursion continues until some condition is met to prevent it.

To prevent infinite recursion, if...else statement (or similar approach) can be used where one branch makes the recursive call, and other doesn't.

7.     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

Initially, the sum() is called from the main() function with number passed as an argument.

Suppose, the value of n inside sum() is 3 initially. During the next function call, 2 is passed to the sum() function. This process continues until n is equal to 0.

When n is equal to 0, the if condition fails and the else part is executed returning the sum of integers ultimately to the main() function.

8.    Program to find factorial of number using Recursion

This Program prompts user for entering any integer number, finds the factorial of input number and displays the output on screen. We will use a recursive user defined function to perform the task. Here we have a function find_factorial that calls itself in a recursive manner to find out the factorial of input number. We have involved the user interaction in the below program, however if you do not want that part then you can simply assign an integer value to variable num and ignore the scanf statement. In short you can tweak it in any way you want, the logic would be the same for each case.

Program to find factorial

/* Program Name: Find Factorial

   Written by: Chaitanya Singh

   Published on: beginnersbook.com

*/

#include<stdio.h>

Int find_factorial(int);

Int main()

{

   int num, fact;

   //Ask user for the input and store it in num

   printf("\nEnter any integer number:");

   scanf("%d",&num);

   //Calling our user defined function

   fact =find_factorial(num);

   //Displaying factorial of input number

   printf("\nfactorial of %d is: %d",num, fact);

   return 0;

}

Int find_factorial(int n)

{

   //Factorial of 0 is 1

   if(n==0)

      return(1);

   //Function calling itself: recursion

   return(n*find_factorial(n-1));

}

Output:

Enter any integer number: 4

Factorial of 4 is: 24

9.     Explain Fibonacci Series

Fibonacci Series in C: In case of fibonacci series, next number is the sum of previous two numbers for example 0, 1, 1, 2, 3, 5, 8, 13, 21 etc. The first two numbers of fibonacci series are 0 and 1.

There are two ways to write the fibonacci series program:

• Fibonacci Series without recursion
• Fibonacci Series using recursion

Fibonacci Series in C without recursion

Let's see the fibonacci series program in c without recursion.

1. #include<stdio.h>    
2. Int main()    
3. {    
4. Int n1=0,n2=1,n3,i,number;    
5. Printf("Enter the number of elements:");    
6. Scanf("%d",&number);    
7. Printf("\n%d %d",n1,n2);//printing 0 and 1    
8. For(i=2;i<number;++i)//loop starts from 2 because 0 and 1 are already printed    
9. {    
10.  n3=n1+n2;    
11.  Printf(" %d",n3);    
12.  n1=n2;    
13.  n2=n3;    
14. }  
15.  Return 0;  
16. }    

Output:

Enter the number of elements:15

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Fibonacci Series using recursion in C

Let's see the fibonacci series program in c using recursion.

1. #include<stdio.h>    
2. Void printFibonacci(int n){    
3.    Static int n1=0,n2=1,n3;    
4.    If(n>0){    
5.         n3 = n1 + n2;    
6.         n1 = n2;    
7.         n2 = n3;    
8.         Printf("%d ",n3);    
9.         PrintFibonacci(n-1);    
10.    }    
11. }    
12. Int main(){    
13.    Int n;    
14.    Printf("Enter the number of elements: ");    
15.    Scanf("%d",&n);    
16.    Printf("Fibonacci Series: ");    
17.    Printf("%d %d ",0,1);    
18.    PrintFibonacci(n-2);//n-2 because 2 numbers are already printed    
19.  Return 0;  
20. }    

Output:

Enter the number of elements:15

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

10. Explain Quick sort or Merge sort with examples

Quick Sort

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.

Implementation in C

#include <stdio.h>

#include <stdbool.h>

#define MAX 7

Int intArray[MAX] = {4,6,3,2,1,9,7};

Void printline(int count) {

   int i;

   for(i = 0;i < count-1;i++) {

      printf("=");

   }

   printf("=\n");

}

Void display() {

   int i;

   printf("[");

   // navigate through all items

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

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

   }

   printf("]\n");

}

Void swap(int num1, int num2) {

   int temp = intArray[num1];

   intArray[num1] = intArray[num2];

   intArray[num2] = temp;

}

Int partition(int left, int right, int pivot) {

   int leftPointer = left -1;

   int rightPointer = right;

   while(true) {

      while(intArray[++leftPointer] < pivot) {

         //do nothing

      }

      while(rightPointer > 0 && intArray[--rightPointer] > pivot) {

         //do nothing

      }

      if(leftPointer >= rightPointer) {

         break;

      } else {

         printf(" item swapped :%d,%d\n", intArray[leftPointer],intArray[rightPointer]);

         swap(leftPointer,rightPointer);

      }

   }

   printf(" pivot swapped :%d,%d\n", intArray[leftPointer],intArray[right]);

   swap(leftPointer,right);

   printf("Updated Array: ");

   display();

   return leftPointer;

}

Void quickSort(int left, int right) {

   if(right-left <= 0) {

      return;  

   } else {

      int pivot = intArray[right];

      int partitionPoint = partition(left, right, pivot);

      quickSort(left,partitionPoint-1);

      quickSort(partitionPoint+1,right);

   }       

}

Int main() {

   printf("Input Array: ");

   display();

   printline(50);

   quickSort(0,MAX-1);

   printf("Output Array: ");

   display();

   printline(50);

}

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

Output

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

==================================================

Pivot swapped :9,7

Updated Array: [4 6 3 2 1 7 9 ]

Pivot swapped :4,1

Updated Array: [1 6 3 2 4 7 9 ]

Item swapped :6,2

Pivot swapped :6,4

Updated Array: [1 2 3 4 6 7 9 ]

Pivot swapped :3,3

Updated Array: [1 2 3 4 6 7 9 ]

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

==================================================

Merge Sort

Merge sort is a sorting technique based on divide and conquer technique. With the worst-case time complexity being Ο(n log n), it is one of the most respected algorithms.

Implementation in C

We shall see the implementation of merge sort in C programming language here −

#include <stdio.h>

#define max 10

Int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };

Int b[10];

Void merging(int low, int mid, int high) {

   int l1, l2, i;

   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {

      if(a[l1] <= a[l2])

         b[i] = a[l1++];

      else

         b[i] = a[l2++];

   }

   while(l1 <= mid)   

      b[i++] = a[l1++];

   while(l2 <= high)  

      b[i++] = a[l2++];

   for(i = low; i <= high; i++)

      a[i] = b[i];

}

Void sort(int low, int high) {

   int mid;

   if(low < high) {

      mid = (low + high) / 2;

      sort(low, mid);

      sort(mid+1, high);

      merging(low, mid, high);

   } else {

      return;

   }  

}

Int main() {

   int i;

   printf("List before sorting\n");

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

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

   sort(0, max);

   printf("\nList after sorting\n");

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

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

}

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

Output

List before sorting

10 14 19 26 27 31 33 35 42 44 0

List after sorting

0 10 14 19 26 27 31 33 35 42 44