UNIT 4

Recursion

4.1 Recursion, as a different way of solving problems

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.

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.

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.

Advantages and Disadvantages of Recursion

Recursion makes program elegant. However, if performance is vital, use loops instead as recursion is usually much slower.

That being said, recursion is an important concept. It is frequently used in data structure and algorithms. For example, it is common to use recursion in problems such as tree traversal.

4.2 Example programs, such as Finding Factorial, Fibonacci series

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

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

4.3 Structures: Defining structures

Why use structure?

In C, there are cases where we need to store multiple attributes of an entity. It is not necessary that an entity has all the information of one type only. It can have different attributes of different data types. For example, an entity Student may have its name (string), roll number (int), marks (float). To store such type of information regarding an entity student, we have the following approaches:

• Construct individual arrays for storing names, roll numbers, and marks.
• Use a special data structure to store the collection of different data types.

Let's look at the first approach in detail.

1. #include<stdio.h>  
2. Void main ()  
3. {  
4.  Char names[2][10],dummy; // 2-dimensioanal character array names is used to store the names of the students   
5.  Int roll_numbers[2],i;  
6.  Float marks[2];  
7.  For (i=0;i<3;i++)  
8.  {  
9.      
10.    Printf("Enter the name, roll number, and marks of the student %d",i+1);  
11.    Scanf("%s %d %f",&names[i],&roll_numbers[i],&marks[i]);  
12.    Scanf("%c",&dummy); // enter will be stored into dummy character at each iteration  
13.  }  
14.  Printf("Printing the Student details ...\n");  
15.  For (i=0;i<3;i++)  
16.  {  
17.    Printf("%s %d %f\n",names[i],roll_numbers[i],marks[i]);  
18.  }  
19. }  

Output

Enter the name, roll number, and marks of the student 1Arun 90 91       

Enter the name, roll number, and marks of the student 2Varun 91 56     

Enter the name, roll number, and marks of the student 3Sham 89 69

Printing the Student details...

Arun 90 91.000000                                                                     

Varun 91 56.000000 

Sham 89 69.000000

The above program may fulfill our requirement of storing the information of an entity student. However, the program is very complex, and the complexity increase with the amount of the input. The elements of each of the array are stored contiguously, but all the arrays may not be stored contiguously in the memory. C provides you with an additional and simpler approach where you can use a special data structure, i.e., structure, in which, you can group all the information of different data type regarding an entity.

What is Structure

Structure in c is a user-defined data type that enables us to store the collection of different data types. Each element of a structure is called a member. Structures ca; simulate the use of classes and templates as it can store various information

The ,struct keyword is used to define the structure. Let's see the syntax to define the structure in c.

1. Struct structure_name   
2. {  
3.    Data_type member1;  
4.    Data_type member2;  
5.    .  
6.    .  
7.    Data_type memeberN;  
8. };  

Let's see the example to define a structure for an entity employee in c.

1. Struct employee  
2. {   int id;  
3.    Char name[20];  
4.    Float salary;  
5. };  

The following image shows the memory allocation of the structure employee that is defined in the above example.

Here, struct is the keyword; employee is the name of the structure; id, name, and salary are the members or fields of the structure. Let's understand it by the diagram given below:

Declaring structure variable

We can declare a variable for the structure so that we can access the member of the structure easily. There are two ways to declare structure variable:

1. By struct keyword within main() function
2. By declaring a variable at the time of defining the structure.

1st way:

Let's see the example to declare the structure variable by struct keyword. It should be declared within the main function.

1. Struct employee  
2. {   int id;  
3.    Char name[50];  
4.    Float salary;  
5. };  

Now write given code inside the main() function.

1. Struct employee e1, e2;  

The variables e1 and e2 can be used to access the values stored in the structure. Here, e1 and e2 can be treated in the same way as the objects in C++ and Java.

2nd way:

Let's see another way to declare variable at the time of defining the structure.

1. Struct employee  
2. {   int id;  
3.    Char name[50];  
4.    Float salary;  
5. }e1,e2;  

Which approach is good

If number of variables are not fixed, use the 1st approach. It provides you the flexibility to declare the structure variable many times.

If no. Of variables are fixed, use 2nd approach. It saves your code to declare a variable in main() function.

Accessing members of the structure

There are two ways to access structure members:

1. By . (member or dot operator)
2. By -> (structure pointer operator)

Let's see the code to access the id member of p1 variable by. (member) operator.

1. p1.id  

C Structure example

Let's see a simple example of structure in C language.

1. #include<stdio.h>  
2. #include <string.h>    
3. Struct employee      
4. {   int id;      
5.    Char name[50];      
6. }e1;  //declaring e1 variable for structure    
7. Int main( )    
8. {    
9.   //store first employee information    
10.   e1.id=101;    
11.   Strcpy(e1.name, "Sonoo Jaiswal");//copying string into char array    
12.   //printing first employee information    
13.   Printf( "employee 1 id : %d\n", e1.id);    
14.   Printf( "employee 1 name : %s\n", e1.name);    
15. Return 0;  
16. }    

Output:

Employee 1 id : 101

Employee 1 name : Sonoo Jaiswal

Let's see another example of the structure in C language to store many employees information.

1. #include<stdio.h>  
2. #include <string.h>    
3. Struct employee      
4. {   int id;      
5.    Char name[50];      
6.    Float salary;      
7. }e1,e2;  //declaring e1 and e2 variables for structure    
8. Int main( )    
9. {    
10.   //store first employee information    
11.   e1.id=101;    
12.   Strcpy(e1.name, "Sonoo Jaiswal");//copying string into char array    
13.   e1.salary=56000;    
14.    
15.  //store second employee information    
16.   e2.id=102;    
17.   Strcpy(e2.name, "James Bond");    
18.   e2.salary=126000;    
19.     
20.   //printing first employee information    
21.   Printf( "employee 1 id : %d\n", e1.id);    
22.   Printf( "employee 1 name : %s\n", e1.name);    
23.   Printf( "employee 1 salary : %f\n", e1.salary);    
24.    
25.   //printing second employee information    
26.   Printf( "employee 2 id : %d\n", e2.id);    
27.   Printf( "employee 2 name : %s\n", e2.name);    
28.   Printf( "employee 2 salary : %f\n", e2.salary);    
29.   Return 0;    
30. }    

Output:

Employee 1 id : 101

Employee 1 name : Sonoo Jaiswal

Employee 1 salary : 56000.000000

Employee 2 id : 102

Employee 2 name : James Bond

Employee 2 salary : 126000.000000

4.4 Array of Structures

Why use an array of structures?

Consider a case, where we need to store the data of 5 students. We can store it by using the structure as given below.

1. #include<stdio.h>  
2. Struct student  
3. {  
4.    Char name[20];  
5.    Int id;  
6.    Float marks;  
7. };  
8. Void main()  
9. {  
10.    Struct student s1,s2,s3;  
11.    Int dummy;  
12.    Printf("Enter the name, id, and marks of student 1 ");  
13.    Scanf("%s %d %f",s1.name,&s1.id,&s1.marks);  
14.    Scanf("%c",&dummy);  
15.    Printf("Enter the name, id, and marks of student 2 ");  
16.    Scanf("%s %d %f",s2.name,&s2.id,&s2.marks);  
17.    Scanf("%c",&dummy);  
18.    Printf("Enter the name, id, and marks of student 3 ");  
19.    Scanf("%s %d %f",s3.name,&s3.id,&s3.marks);  
20.    Scanf("%c",&dummy);  
21.    Printf("Printing the details....\n");  
22.    Printf("%s %d %f\n",s1.name,s1.id,s1.marks);  
23.    Printf("%s %d %f\n",s2.name,s2.id,s2.marks);  
24.    Printf("%s %d %f\n",s3.name,s3.id,s3.marks);  
25. }  

Output

Enter the name, id, and marks of student 1 James 90 90 

Enter the name, id, and marks of student 2 Adoms 90 90 

Enter the name, id, and marks of student 3 Nick 90 90      

Printing the details....       

James 90 90.000000                         

Adoms 90 90.000000                     

Nick 90 90.000000

In the above program, we have stored data of 3 students in the structure. However, the complexity of the program will be increased if there are 20 students. In that case, we will have to declare 20 different structure variables and store them one by one. This will always be tough since we will have to declare a variable every time we add a student. Remembering the name of all the variables is also a very tricky task. However, c enables us to declare an array of structures by using which, we can avoid declaring the different structure variables; instead we can make a collection containing all the structures that store the information of different entities.

Array of Structures in C

An array of structures in C can be defined as the collection of multiple structures variables where each variable contains information about different entities. The array of structure in C are used to store information about multiple entities of different data types. The array of structures is also known as the collection of structures.

Let's see an example of an array of structures that stores information of 5 students and prints it.

1. #include<stdio.h>  
2. #include <string.h>    
3. Struct student{    
4. Int rollno;    
5. Char name[10];    
6. };    
7. Int main(){    
8. Int i;    
9. Struct student st[5];    
10. Printf("Enter Records of 5 students");    
11. For(i=0;i<5;i++){    
12. Printf("\nEnter Rollno:");    
13. Scanf("%d",&st[i].rollno);    
14. Printf("\nEnter Name:");    
15. Scanf("%s",&st[i].name);    
16. }    
17. Printf("\nStudent Information List:");    
18. For(i=0;i<5;i++){    
19. Printf("\nRollno:%d, Name:%s",st[i].rollno,st[i].name);    
20. }    
21.   Return 0;    
22. }    

Output:

Enter Records of 5 students

Enter Rollno:1

Enter Name:Sonoo

Enter Rollno:2

Enter Name:Ratan

Enter Rollno:3

Enter Name:Vimal

Enter Rollno:4

Enter Name:James

Enter Rollno:5

Enter Name:Sarfraz

Student Information List:

Rollno:1, Name:Sonoo

Rollno:2, Name:Ratan

Rollno:3, Name:Vimal

Rollno:4, Name:James

Rollno:5, Name:Sarfraz

Reference:

1. Byron Gottfried, Schaum's Outline of Programming with C, McGraw-Hill

2. A.K. Sharma, Computer Fundamentals and Programming in C, Universities Press, 2nd Edition, 2018.

3. E. Balaguruswamy, Programming in ANSI C, Tata McGraw-Hill

4. Brian W. Kernighan and Dennis M. Ritchie, the C Programming Language, Prentice Hall of India.