Unit - 3

Function and Recursion

3.1 Functions (including using built in libraries)

A function which is predefined in c language is called a library function. Library function is also called a built-in function of C language. The definition of the library function is stored in the respective header file. Library functions are used to perform dedicated operations like taking input from the user, displaying output, string handling operation, etc. Library functions are readily available and programmers can directly use it without writing any extra code. For example, printf () and scanf () are library functions and their definition is stored in the stdio header file.

2.     User Defined Functions

User defined function is the block of code written by a programmer to perform a particular task. The compiler doesn’t have any idea about the user defined function so the programmer has to define and declare these functions inside the program body. Programmers can define these functions outside the main function but declaration of user defined function should be present in main function only. Whenever the compiler executes function call (function declaration) then compiler shift the flow of program execution to the definition part of user defined function.

Example

#include<stdio.h>

#include<conio.h>

int add(int x, int y)

{

int sum;

sum = x + y;

return (sum);

}

main()

{

int a,b,c;

a = 15;

b = 25;

c = add (a,b);

printf(“\n Addition is %d”, c);

}

Output:

Addition is 40

There are two ways to pass the parameters to the function

2.     Parameter Passing by reference : In this mechanism, the address of the parameter is passed while calling the function.

Key takeaway :

3.2 Parameter passing in functions, call by value

Parameter Passing by Value

This is the default way of passing the parameters to the function. This is achieved by passing the copy of data to the function. This mechanism is also called as call by value. In case of parameter passing by value, the changes made to the formal arguments in the called function have no effect on the values of actual arguments in the calling function.

This mechanism is used when programmers don't want to change the value of passed parameters. When parameters are passed by value then functions in C create copies of the passed in variables and do required processing on these copied variables.

Pass-by-value is implemented by actual data transfer so additional storage is required to maintain the copies of passed parameters.

Example:

#include<stdio.h>

#include<conio.h>

/* function declaration goes here */

void swap(int p1, int p2);

int main()

{

 int a =10;

 int b =20;

 printf(“Before: value of a = %d and value of b = %d\n”, a,b);

 swap(a,b);

 printf(“After : value of a = %d and value of b = %d\n”, a,b);

 getch();

}

void swap(int p1, int p2)

{

 int t;

 t = p2;

 p2 = p1;

 p1 = t;

 printf(“Value of a (p1) = %d and value of b(p2) = %d\n”, p1,p2);

}

Output :

Before: Value of a = 10 and value of b = 20

Value of a (p1) = 20 and value of b (p2) = 10

After: Value of a = 10 and value of b = 20

Note: In the above example the values of “a” and “b” remain unchanged before calling swap function and after calling swap function.

Key takeaway :

3.3 Passing arrays to functions: idea of call by reference

Array is a data structure which stores the collection of similar types of elements in consecutive memory locations. Indexing of arrays always starts with ‘0’ whereas non-graphical variable ‘\0’ indicates the end of the array. Syntax for declaring array is

data type array name[Maximum size];

●      Data types are used to define the type of element in an array. Data types are also useful in finding the size of total memory locations allocated for the array.

●      All the rules of defining the name of a variable are also applicable for the array name.

●      Maximum size indicates the total number of maximum elements that an array can hold.

●      Total memory allocated for the array is equal to the memory required to store one element of the array multiplied by the total element in the array.

●      In an array, memory allocation is done at the time of declaration of an array.

Example:

This is the default way of passing the parameters to the function. This is achieved by passing the copy of data to the function. This mechanism is also called as call by value. In case of parameter passing by value, the changes made to the formal arguments in the called function have no effect on the values of actual arguments in the calling function.

This mechanism is used when programmers don't want to change the value of passed parameters. When parameters are passed by value then functions in C create copies of the passed in variables and do required processing on these copied variables.

Pass-by-value is implemented by actual data transfer so additional storage is required to maintain the copies of passed parameters.

Parameter Passing by Reference

This mechanism is used when programmers want a function to do the changes in passed parameters and reflect those changes back to the calling function. This mechanism is also called a call by reference. This is achieved by passing the address of the variable to the function and function body can directly work over the addresses. Advantage of pass by reference is efficiency in both time and space. Whereas disadvantages are access to formal parameters is slow and inadvertent and erroneous changes may be made to the actual parameter.

Example:

#include<stdio.h>

#include<conio.h>

void swap(int *p1, int *p2);

int main()

{

 int a =10;

 int b =20;

 printf(“Before: value of a = %d and value of b = %d\n”, a,b);

 swap(&a, &b);

 printf(“After : value of a = %d and value of b = %d\n”, a,b);

 getch();

}

void swap(int *p1, int *p2)

{

 int t;

 t = *p2;

 *p2 = *p1;

 *p1 = t;

 printf(“Value of a (p1) = %d and value of b(p2) = %d\n”, *p1, *p2);

}

Output :

Before: Value of a = 10 and value of b = 20

Value of a (p1) = 20 and value of b(p2) = 10

After: Value of a = 20 and value of b = 10

Note: In the above example the values of “a” and “b” are changed after calling the swap function.

Key takeaway :

3.4 Recursion as a different way of solving problems

When a function calls a copy of itself to operate on a smaller problem, the mechanism is known as recursion. A recursive function is one that calls itself, and such function calls are referred to as recursive calls. There are some recursive calls in recursion. It is, however, important to enforce a recursion termination condition. While recursion code is shorter than iterative code, it is more difficult to comprehend.

Recursion cannot be used to solve all problems; however, it is more useful for tasks that can be broken down into smaller subtasks. Recursion can be used to solve problems like sorting, searching, and traversal.

Since function calls are still overhead, iterative solutions are generally more effective than recursion. Any problem can be solved iteratively if it can be solved recursively. However, some problems, such as the Tower of Hanoi, the Fibonacci sequence, and factorial finding, are better solved by recursion.

3.5 Example programs such as Finding Factorial, Fibonacci series, Ackerman function etc

Such as Finding Factorial

The factorial of a positive number is the product of the integral values from 1 to the number itself.

Eg. 5!=5*4*3*2*1

  120

Recursive Factorial:

 The factorial algorithm can be defined recursively as follows

Factorial(n) =    1      if n=0

   n*(Factorial(n-1))   if n>0 

Algorithm:

Calculate factorial of n

   fact(n) 

return 1

2.  else

return(n*fact(n-1))

3.  endif

end fact(n)

Fig 1: recursion of factorial number

Program to find factorial of a number using recursion.

#include<stdio.h>

#include<conio.h>

int rec (int x);

void main()

{

int a, fact;

printf("\nEnter any number: ");

scanf ("%d", &a);

fact=rec(a);

printf("\nFactorial Value = %d", fact);

getch();

}

int rec (int x)

{

int f;

if (x==1)

return (1);

else

f=x*rec(x-1);

return (f);

}

Such as fibonacci series  

The first two numbers of the Fibonacci series are 0,1. The next number is the sum of the previous two numbers.

  Eg.   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

●      1 is calculated by adding previous two numbers(0+1)

●      2 is calculated by adding the two numbers before it (1+1)

●      Similarly, the 3 is found by adding the two numbers before it (1+2), and so on

Algorithm:

 int fib(int n)

 {

  return n;

2.  else

  return (fib(n-1) + fib(n-2));

 }

Fig 1: fibonacci series

Program to print Fibonacci series using recursion.

#include<stdio.h>

#include<conio.h>

int Fibonacci(int);

void main()

{

   int n, i, c=0;// n is no. of terms in Fibonacci series.

   printf(“Enter no. of terms in Fibonacci series”);

   scanf("%d",&n);

   printf("Fibonacci series\n");

   for( i= 1 ; i <= n ; i++ )

   {

   printf("%d\n", Fibonacci(c));

   c++;

   }

   getch();

}

int Fibonacci(int x)

{

   if ( x == 0 )

   return 0;

   else if ( x == 1 )

   return 1;

   else

   return ( Fibonacci(x-1) + Fibonacci(x-2) );

}

Such as Ackermann function

The Ackermann function is the most basic example of a well-defined total function that is computable but not primitive recursive, serving as a counterexample to the early 1900s assumption that any computable function was also primitive recursive. It grows at a faster rate than an exponential or multiple exponential function.

The source code for a C program to implement the Ackermann function using recursion is shown below, which has been successfully compiled and run on a Windows system to generate the desired output:

Program  to implement Ackermann function using Recursion:

/* C Program to implement Ackermann function using recursion */

#include<stdio.h>

int A(int m, int n);

main()

{

        int m,n;

        printf("Enter two numbers :: \n");

        scanf("%d%d",&m,&n);

        printf("\nOUTPUT :: %d\n",A(m,n));

}

int A(int m, int n)

{

        if(m==0)

                return n+1;

        else if(n==0)

                return A(m-1,1);

        else

                return A(m-1,A(m,n-1));

}

Output :

Enter two numbers ::

1

0

OUTPUT :: 2

Key takeaway :

3.6 Quick sort or Merge sort 

Quick sort is the most efficient method of sorting .It uses divide and conquer strategy to sort the elements. In quicksort, we divide the array of items to be sorted into two partitions and then call the quicksort procedure recursively to sort the two partitions. For this we choose a pivot element and arrange all elements such that all the elements in the left part are less than the pivot and all those in the right part are greater than it.

Algorithm to implement Quick Sort is as follows.

Consider array A of size n to be sorted. p is a pivot element. Index positions of the first and last element of array A are denoted by ‘first’ and ‘last’.

C function for Quick sort

x = 0,  y = n-1

void Quicksort(A,x,y)

{

if(x<y)

{

first=x;

last=y;

while(first<last)

{

while(A[first]<p)

first++;

while(A[last]>p)

last--;

if(first<last)

swap(A[first],A[last]);

}

swap(A[x],A[y])

Quicksort(A,x,last-1);

Quicksort(A,first+1,y);

}

Example : Apply Quicksort on array

 A= {27,6,39,2,65,12,57,18,49,19}

Here again first<last so we swap A[first] and A[last]. Swapping 65 and 18 we get

Repeat steps 2,3 and 4.

Now First>last so we swap pivot p with A[last]. Swapping 27 and 12 we get

Here we complete Pass 1.Now pivot element is 27 and it divides the array in left and right partitions. We can see that elements less than pivot are in the left partition and elements greater than pivot are in the right partition.

Now we continue the same procedure for the left and right partition.  Here we see results of corresponding passes.

Pass 2 :

Pass 3 :

Pass 4 :

Pass 5 :

Pass 6 :

Pass 7 :

Merge sort 

Merge sort consisting two phases as divide and merge.

●  In the divide phase, each time it divides the given unsorted list into two sublists until each sub list gets a single element then sorts the elements.

●  In the merge phase, it merges all the solutions of sub lists and finds the original sorted list.

Features :

●   Is an algorithm dependent on comparison?

●   A stable algorithm is

●   A fine example of the strategy of divide & conquer algorithm design

●   John Von Neumann invented it.

Steps to solve the problem:

Step 1: if the length of the given array is 0 or 1 then it is already sorted, else follow  step 2.

Step 2: split the given unsorted list into two half parts

Step 3: again divide the sub list into two parts until each sub list get single element

Step 4: As each sub list gets the single element compare all the elements with each other & swap in between the elements.

Step 5: merge the elements same as divide phase to get the sorted list

 Algorithm:

Example:

Apply merge sort for the following list of elements: 38, 27, 43, 3, 9, 82, 10

Analysis of merge sort:

Complexity of Merge Sort :

Time to mergesort N elements = Time to mergesort N/2 elements plus time to merge two arrays each N/2 elements.

Time to merge two arrays each N/2 elements is linear, i.e. N

Advantages

●   The number of comparisons carried out is almost ideal.

●   Mergesort is never going to degrade to O (n2)

●   It is applicable to files of any size.

Limitations

●   Using extra memory O(n).

Key takeaways :

 References :