Description

Assignment 1 : Development of module and library

Problem 1: Recursion
Write Recursive Functions in C for each of the tasks stated below. Also write main functions to demonstrate each of those functions.

Background Theory
Definition: An algorithm or function is recursive if it refers (calls) itself directly or indirectly.
Eg,
1. function F1 calls F1 directly
2. function F1 calls F2 and F2, in turn, calls F1. F1, thus, calls F1 indirectly.

Recursion is a totally different method of solving problems. Conventional problem solving methods consists of decomposing the solution into steps, and executing each step in turn. The recursive way of solving a problem, on the other hand, is to reduce the problem into another problem that is exactly of the same type but simpler, and solving the new one instead. And how to solve the new one? It is just reduced into another simpler problem of exactly the same type, and so on, and so on, and so on…

Principle behind designing (developing) recursive algorithm (function): Step 1. If the problem is too simple, solve it straight way [Basis Step]
Step 2. Otherwise beak the problem into similar but simpler problem with the target that at some point of time it will be simple enough to be solved straight way. [Recursion Step]

Problems
A. String comparison:Compare strings s1 and s2 – print 0 if both are same, print -1 if alphabetically s1 comes before s2 and print 1 if alphabetically s1 comes after s2.
If s1 and s2 both are empty strings then print 0. If the 1st character of s1 alphabetically comes before the 1st character of s2 print -1. If the 1st character of s1 alphabetically comes after the 1st character of s2 print 1. [Step 1]
Else compare the rest of s1 with rest of s2 (that is, other than the 1 st characters, the remaining parts of s1 and s2,) [Step 2]

B. Find largest among n integers
If n = 1 then the single integer itself is the largest [Step 1]
Else the largest integer is the larger one between the last integer and largest among the remaining integers. [Step 2]

C. Search for a given integer num in a given list L of n integers (returns true if num occurs in L, otherwise returns false).
If n = 0, that is L is empty, then return false. If the first item of L is num then return true.
[Step 1]
Else search for num in the remaining list of (n-1) integers (that is L without the first item) [Step 2]

D. Print a given list L of n items in reverse order
If n = 0, that is, L is empty, then do not print anything. [Step 1]
Else print the last item followed by print the remaining list of (n-1) items in reverse order (that is L without the last item) [Step 2]

E. Find out whether the given string S of length n is a palindrome or not (returns true if S is a palindrome, returns false otherwise). [A palindrome is a string if it reads same from both the ends. Eg. ABCDCBA]
If n=0 or n=1, that is, S is empty or has a single character, then return true. [Step 1] If the first and last characters of S are different then return false, else find out whether the remaining string (S without the first and last characters) is a palindrome or not. [Step 2]

F. Replace all occurrences of the character c1 in the string S by the character c2.
If S is empty, then, do not do anything. [Step 1]
Else if the first character of S is c1, then replace it by c2. Replace all occurrences of the character c1 in the remaining string (S without the first character) by the character c2. [Step 2]

G. Sorting an array A of n integers in ascending order.
If n is 1, then, do not do anything. [Step 1]
Else
Find i so that A[i] is largest and then interchange A[i] and A[n] and Sort first n-1 elements of A. [Step 2]

Problem 2: Concept of Module
Prepare a module (a single .c file) that consists of all of these above 7 functions. If you need any other functions, then those functions should not be accessible from outside that file.

Write the client code (file with main() function) that should include header file (APIs) supplied by the module. The client code should demonstrate functionalities of all the above stated 7 functions.

Note: Here reuse of existing code is encouraged. Don’t rewrite code again and again. You are also encouraged to create more than one module (like some functions in one .c file and rest of the functions in another .c file) if you feel necessary.

Problem 3: Concept of Static library
Prepare a static library using the module as mentioned in problem 2. Then build a final executable using the static library and the client code.