Lecture Notes on Modular Programming and Recursion
1. Introduction to Modular Programming
Modular programming is a design technique that focuses on dividing a program into
small, manageable, and independent units, known as "modules." Each module performs
a specific task and can be developed, tested, and debugged independently, allowing for
reusability and efficient problem-solving.
● Advantages of Modular Programming:
○ Simplified Code: Breaking down code into modules makes it easier to
read and manage.
○ Reusability: Modules can be reused in different parts of the program or in
different programs.
○ Improved Testing and Debugging: Modules can be tested independently,
making it easier to locate and fix bugs.
○ Collaboration: Allows multiple programmers to work on different parts
of a program simultaneously.
● Modularization Techniques:
○ Functions: Group a series of statements to perform a specific task.
○ Files and Libraries: Separate code across multiple files or packages.
○ Encapsulation: Use data structures and algorithms that only expose
necessary information to other parts of the program.
2. Recursion in Modular Programming
Recursion is a technique in which a function calls itself to solve a problem. It is
especially useful for solving problems that can be broken down into smaller sub-
problems of the same type, such as searching and sorting algorithms.
● Recursive Approach:
○ Base Case: The condition that stops the recursion.
○ Recursive Case: The function calls itself with modified parameters to
work toward the base case.
● Advantages of Recursion:
○ Simplifies Complex Problems: Problems like factorial calculation,
Fibonacci series, and certain searches/sorts are easier to express
recursively.
○ Reduces Code Size: Some problems require fewer lines of code when
written recursively.
● Examples of Recursive Algorithms:
○ Binary Search
○ Merge Sort
○ Factorial Calculation
3. Sorting Algorithms in Modular Programming
Sorting is a fundamental task in computer science, where we arrange data in a specific
order. Here are two basic sorting algorithms commonly covered in introductory
programming.
3.1 Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list,
compares adjacent elements, and swaps them if they are in the wrong order.
● Algorithm:
○ Start from the first element and compare each pair of adjacent elements.
○ Swap elements if they are in the wrong order.
○ Repeat the process until the entire list is sorted.
● Complexity:
○ Time Complexity: O(n2)O(n^2)O(n2)
○ Space Complexity: O(1)O(1)O(1) (in-place sorting)
Implementation (Modularized):
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
3.2 Selection Sort
Selection Sort is another simple sorting algorithm that repeatedly finds the minimum
element from the unsorted part and moves it to the beginning.
● Algorithm:
○ Start from the first element and search for the smallest element in the
array.
○ Swap the smallest element with the current element.
○ Repeat for each position in the array.
● Complexity:
○ Time Complexity: O(n2)O(n^2)O(n2)
○ Space Complexity: O(1)O(1)O(1) (in-place sorting)
Implementation (Modularized):
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
4. Searching Algorithms in Modular Programming
Searching algorithms are used to find an element within a data structure. Here, we
cover two common types: Linear Search and Binary Search.
4.1 Linear Search
Linear Search is a straightforward algorithm that checks each element of the list until it
finds the target element.
● Algorithm:
○ Traverse the array one element at a time.
○ If an element matches the target, return its index.
○ If no match is found, return -1 to indicate the target is not in the array.
● Complexity:
○ Time Complexity: O(n)O(n)O(n)
○ Space Complexity: O(1)O(1)O(1)
Implementation (Modularized):
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
4.2 Binary Search
Binary Search is a faster algorithm that works on sorted arrays by repeatedly dividing
the search range in half.
● Algorithm (Recursive Version):
○ Compare the target with the middle element of the array.
○ If the target is equal to the middle element, return its index.
○ If the target is smaller, repeat the search on the left half of the array.
○ If the target is larger, repeat the search on the right half of the array.
○ If the target is not found, return -1.
● Complexity:
○ Time Complexity: O(logn)O(\log n)O(logn)
○ Space Complexity: O(logn)O(\log n)O(logn) for the recursive version due
to call stack.
Implementation (Recursive Modularized):
int binarySearch(int arr[], int left, int right, int target) {
if (right >= left) {
int mid = left + (right - left) / 2;
// Check if the target is present at the mid
if (arr[mid] == target) {
return mid;
}
// If target is smaller than mid, search the left subarray
if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
}
// Else search the right subarray
return binarySearch(arr, mid + 1, right, target);
}
// Target is not present in the array
return -1;
}
5. Conclusion
● Modular Programming: By breaking down a program into smaller modules, it
becomes easier to understand, test, and reuse.
● Recursion: Useful for tasks that involve repetitive, self-similar calculations, such
as Binary Search.
● Sorting and Searching: Basic algorithms like Bubble Sort, Selection Sort, Linear
Search, and Binary Search serve as essential building blocks in many
applications.
Each module can be independently modified, tested, and debugged, providing a clear
and structured approach to solving problems in C programming.
Programs Using Functions:
1. Factorial Calculation
○ Function to calculate the factorial of a number using recursion and using a
loop.
2. Prime Number Checker
○ Function to check if a given number is prime.
3. Fibonacci Sequence
○ Function to print the Fibonacci sequence up to n terms, both iteratively
and recursively.
4. Greatest Common Divisor (GCD)
○ Function to find the GCD of two numbers using Euclid’s algorithm with
recursion.
5. Palindrome Check
○ Function to check if a given string or number is a palindrome using
recursion.
6. Power Calculation
○ Recursive function to calculate x^y (where x is the base and y is the
exponent).
7. Sum of Natural Numbers
○ Recursive function to calculate the sum of the first n natural numbers.
8. Tower of Hanoi
○ Recursive solution for the Tower of Hanoi problem with three pegs.
9. Binary Search
○ Recursive function to perform binary search on a sorted array.
10. Reverse Array Using Recursion
● Recursive function to reverse the elements of an array.