Hi! This is not a tutorial, though I'll explain any code I post here. On this blog I post source codes of various programs I have written, though the questions/programming problems may or may not be my own. These include solutions to some questions of some good books too. Not too language specific, since I'll be posting codes in C, C++, Java, C#, etc. For contact information, see my Disclosure Policy, for more info, check out my first post: http://letsplaycoding.blogspot.com/2014/03/welcome.html
Quick Sort is considered an intermediate level sorting algorithm, from implementation complexity perspective. Usually, it is taught to students once they are familiar with basic programming constructs and recursion. The quick sort algorithm is better than selection or bubble sort algorithms because of the space-time complexity, which reduces from quadratic to logarithmic, due to continuous division of the data set. However, in the worst-case scenario, the complexity tends to be quadratic, so it may not be the best algorithm always. This algorithm is used to demonstrate recursion and divide and conquer problem solving techniques.
A question may arise here if it is possible to implement quick sort without recursion, and the answer is yes. However, in this post today, we are going to implement it via recursion.
In quick sort, the program identifies an element, called 'pivot', and sorts the list around this pivot value. There are various ways to identify the first pivot to start with. One popular method is to choose the first or the last element as pivot. In this post, we are going to use the last element as initial pivot. Once a pivot value is chosen, the algorithm tries to place this pivot value at position better than its current position. It does so by partitioning the list around the pivot (one list of value before pivot and other list after the pivot), putting values less than pivot one by one, thus shifting the values higher than pivot. At the end, the values of initial pivot and the value next to the last index where the value was swapped are exchanged, and the new position of pivot element is the new pivot index. Now we have two lists, one to the left of the pivot and one to the right. The algorithm then quicksorts the left list and the right list, by recursively calling itself.
To understand quick sort better, consider a list of 5 numbers, [5, 3, 2, 1, 4]. Following is how quick sort would sort the list. The blue-colored box represent the pivot.
Unlike insertion/selection/bubble sort, the problem is solved by dividing and conquering the data set, hence sorting the list incrementally.
int partition (int inputArray[], int startIndex, int inputArrayLength)
{
int valueAtPivot = inputArray[inputArrayLength];
int leastIndex = startIndex - 1;
int loopVar, exchangeSpace;
void quickSort(int inputArray[], int startIndex, int inputArrayLength)
{
if (startIndex < inputArrayLength)
{
int pivotIndex = partition (inputArray, startIndex, inputArrayLength);
quickSort (inputArray, startIndex, pivotIndex - 1);
quickSort (inputArray, pivotIndex + 1, inputArrayLength);
}
}
int main()
{
int userChoice, outerLoop, lengthNumberList = 0, originalNumberList[25], sortedNumberList[25];
printf ("Welcome to SortingAlgorithms v1.4\n");
printf ("Made by Toxifier\n");
do
{
printf ("\n1: Add an element to the list\n");
printf ("2: Display Original List\n");
printf ("3: Perform Quick Sort\n");
printf ("4: Empty List\n");
printf ("5: Exit\n");
printf ("Enter your choice: ");
scanf ("%d", &userChoice);
switch (userChoice)
{
case 1:
if (lengthNumberList >= 25)
{
printf ("\nArray Full\n");
}
else
{
printf ("\nEnter the value: ");
scanf ("%d", &originalNumberList[lengthNumberList]);
sortedNumberList[lengthNumberList] = originalNumberList[lengthNumberList];
lengthNumberList++;
}
break;
case 2:
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
printf ("\nOriginal List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", originalNumberList[outerLoop]);
}
}
break;
case 3:
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
quickSort (sortedNumberList, 0, lengthNumberList - 1);
printf ("\nSorted List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", sortedNumberList[outerLoop]);
}
}
break;
case 4:
lengthNumberList = 0;
break;
case 5:
printf ("Thank You for using SortingAlgorithms v1.4\n");
printf ("Made by Toxifier\n");
break;
default:
printf ("\nWrong Choice!\n");
break;
}
}
while (userChoice != 5);
system("pause");
return 0;
}
Explanation of Code
#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H
int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.
printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.
scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.
int userChoice, outerLoop, lengthNumberList = 0, originalNumberList[25], sortedNumberList[25]; -> Here we define the variables we are going to use in our program.
userChoice is used for the switch and do-while loop. The program is menu driven to allow user to change the array and move in any order they wish to.
outerLoop is the loop variable.
lengthNumberList is used to track the final position of the arrays. originalNumberList[25], sortedNumberList[25] are the arrays which will hold the user input and the sorted list, respectively.
This is the first case of the program where the user inputs the array values. Since the array is defined with maximum length of 25, an error is thrown to the user and they are not allowed to add more values to the list once the limit is reached.
If the array has enough space though, the user can proceed further and input a value to the array, which will get stored at the end of the list. Every user input is copied to the sortedNumberList as well, so that original list is intact for future reference.
This is the second case of our program which is used to display the list created by the user so far. The code iterates through the array, originalNumberList and prints each element.
This is the third case of our program where we have the problem statement addressed - implementing the quick sort algorithm. We first check the length of the array, and proceed with sorting only if there are any elements. The program then calls the function quickSort to sort the list. Once the list is sorted, it is displayed.
It is important to note that we are working on the sortedNumberList array instead of the originalNumberList array. The idea is to preserve the original list for any reference.
When implementing quick sort, this code and the two functions partition and quickSort are good enough to solve the problem. Rest of the code in our C program is only having a few useful additions which helps in easy execution of the program, making it more user friendly.
void quickSort(int inputArray[], int startIndex, int inputArrayLength)
{
if (startIndex < inputArrayLength)
{
int pivotIndex = partition (inputArray, startIndex, inputArrayLength);
quickSort (inputArray, startIndex, pivotIndex - 1);
quickSort (inputArray, pivotIndex + 1, inputArrayLength);
}
}
The function quickSort expects 3 parameters. The array to be sorted (int inputArray[]); the starting point of the array for the function call (int startIndex); and the length of the array (int inputArayLength).
This function implements Quick Sort algorithm in a recursive manner (note the function calls itself). The function only works if there are more than 1 elements in the list. It would call the function partition to move the pivot element to a better place than it is at right now (last position), and retrieve the index of the new place where the pivot element is moved to. It then calls itself, first on the list to the left of pivot, then on the list to right of the pivot. Eventually dividing the list and working upon the sub-lists.
When calling itself recursively, quickSort keeps dividing the list it works upon further, until the list reduces to unit size. Hence, the entire logic is wrapped under an if condition, which says that the function should do something only if the starting position of the array is less than the number of elements in the list, basically giving the control back to the previous recursive call upon encountering a single element sub-array.
int partition (int inputArray[], int startIndex, int inputArrayLength)
{
int valueAtPivot = inputArray[inputArrayLength];
int leastIndex = startIndex - 1;
int loopVar, exchangeSpace;
The function partition is the place where actual sorting of elements happen. The function puts the elements smaller than the pivot one by one, shifting the larger values further down the list and finally exchanging the first largest value from its last position after shifting, with the pivot value. The function then returns the new index of the pivot. Since the function quickSort calls this function for smaller lists, the overall lists eventually gets sorted with a combination of these two functions.
The function partition accepts three arguments: int inputArray[] (the address of the array being worked upon), int startIndex (the index of the first element of the sub-list), int inputArrayLength (the length of the sublist).
Additionally, we have a bunch of variables defined to aid in the process. int valueAtPivot that holds the value of the pivot element; int leastIndex which is used to track the position at which the next element needs to be put at; int loopVar, exchangeSpace which are used to loop through the sub-list and to exchange the values when needed.
Next, the for loop iterates through the sub-list and keep shifting any elements higher than pivot down the list. It is important to note, the values are not put at the correct position in one go, they eventually land in place. Hence, in worst case scenario, the list gets iterated multiple times, causing quadratic complexity of the algorithm. After the loop, int leastIndex is pointing to the index at which the first high element is placed at in the end. The function then exchanges the value at this index and that at original pivot and returns the new index of pivot to work further.
The combination of quickSort and partition calls, eventually sorts the entire array.
lengthNumberList = 0; -> This is the fourth case where we reset the lengthNumberList variable, which tracks the last element of the array. This helps in giving the user ability to redo any operation, without the need of closing and starting the program again.
printf ("Thank You for using SortingAlgorithms v1.4\n");
printf ("Made by Toxifier\n");
This is the fifth case statement, which allows the user to safely exit the program.
default:
printf ("\nWrong Choice!\n");
When using the case statement, it is important to use the break keyword at the end of each case to avoid the program from falling through the next case. It is also important to note the default case, which is important to handle any wrong values in the switch-case logic.
system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.
Merge Sort is considered an intermediate level sorting algorithm, from implementation complexity perspective. Usually, it is taught to students once they are familiar with basic programming constructs and recursion. The merge sort algorithm is better than selection or bubble sort algorithms because of the space-time complexity, which reduces from quadratic to logarithmic, due to continue division of the data set. This algorithm is used to demonstrate recursion and divide and conquer problem solving techniques.
A question may arise here if it is possible to implement merge sort without recursion, and the answer is yes. However, in this post today, we are going to implement it via recursion.
In merge sort the program the program divides the list into smaller sub-lists, and continues to do so until it is left with unit sized lists. It then takes two sublists, sorts their elements, and continues to work up by combining smaller sublist and sorting them.
To understand merge sort better, consider a list of 5 numbers, [5, 3, 2, 1, 4]. Following is how merge sort would sort the list. The blue-colored boxes represent the left sub-list in the iteration and pink boxes represent the right sub-array.
Unlike insertion/selection/bubble sort, the problem is solved by dividing and conquering the data set, hence sorting the list incrementally.
void merge(int inputArray[], int startIndex, int medianIndex, int inputArrayLength)
{
int leftLoop, rightLoop, remainderLoop;
int leftArrayLength = medianIndex - startIndex + 1;
int rightArrayLength = inputArrayLength - medianIndex;
int leftArray[leftArrayLength], rightArray[rightArrayLength];
void mergeSort(int inputArray[], int startIndex, int inputArrayLength)
{
if (startIndex < inputArrayLength)
{
int medianIndex = startIndex + (inputArrayLength - startIndex) / 2;
mergeSort (inputArray, startIndex, medianIndex);
mergeSort (inputArray, medianIndex + 1, inputArrayLength);
merge (inputArray, startIndex, medianIndex, inputArrayLength);
}
}
int main()
{
int userChoice, outerLoop, lengthNumberList = 0, originalNumberList[25], sortedNumberList[25];
printf ("Welcome to SortingAlgorithms v1.3\n");
printf ("Made by Toxifier\n");
do
{
printf ("\n1: Add an element to the list\n");
printf ("2: Display Original List\n");
printf ("3: Perform Merge Sort\n");
printf ("4: Empty List\n");
printf ("5: Exit\n");
printf ("Enter your choice: ");
scanf ("%d", &userChoice);
switch (userChoice)
{
case 1:
if (lengthNumberList >= 25)
{
printf ("\nArray Full\n");
}
else
{
printf ("\nEnter the value: ");
scanf ("%d", &originalNumberList[lengthNumberList]);
sortedNumberList[lengthNumberList] = originalNumberList[lengthNumberList];
lengthNumberList++;
}
break;
case 2:
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
printf ("\nOriginal List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", originalNumberList[outerLoop]);
}
}
break;
case 3:
if (lengthNumberList == 0)
{
printf ("\nList Empty!\n");
}
else
{
mergeSort (sortedNumberList, 0, lengthNumberList - 1);
printf ("\nSorted List: ");
for (outerLoop = 0; outerLoop < lengthNumberList; outerLoop++)
{
printf ("%d ", sortedNumberList[outerLoop]);
}
}
break;
case 4:
lengthNumberList = 0;
break;
case 5:
printf ("Thank You for using SortingAlgorithms v1.3\n");
printf ("Made by Toxifier\n");
break;
default:
printf ("\nWrong Choice!\n");
break;
}
}
while (userChoice != 5);
system("pause");
return 0;
}
Explanation of Code
#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H
int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So, I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.
printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.
scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.
int userChoice, outerLoop, lengthNumberList = 0, originalNumberList[25], sortedNumberList[25]; -> Here we define the variables we are going to use in our program.
userChoice is used for the switch and do-while loop. The program is menu driven to allow user to change the array and move in any order they wish to.
outerLoop is the loop variable.
lengthNumberList is used to track the final position of the arrays. originalNumberList[25], sortedNumberList[25] are the arrays which will hold the user input and the sorted list, respectively.
This is the first case of the program where the user inputs the array values. Since the array is defined with maximum length of 25, an error is thrown to the user and they are not allowed to add more values to the list once the limit is reached.
If the array has enough space though, the user can proceed further and input a value to the array, which will get stored at the end of the list. Every user input is copied to the sortedNumberList as well, so that original list is intact for future reference.
This is the second case of our program which is used to display the list created by the user so far. The code iterates through the array, originalNumberList and prints each element.
This is the third case of our program where we have the problem statement addressed - implementing the merge sort algorithm. We first check the length of the array, and proceed with sorting only if there are any elements. The program then calls the function mergeSort to sort the list. Once the list is sorted, it is displayed.
It is important to note that we are working on the sortedNumberList array instead of the originalNumberList array. The idea is to preserve the original list for any reference.
When implementing merge sort, this code and the two functions merge and mergeSort are good enough to solve the problem. Rest of the code in our C program is only having a few useful additions which helps in easy execution of the program, making it more user friendly.
void mergeSort(int inputArray[], int startIndex, int inputArrayLength)
{
if (startIndex < inputArrayLength)
{
int medianIndex = startIndex + (inputArrayLength - startIndex) / 2;
mergeSort (inputArray, startIndex, medianIndex);
mergeSort (inputArray, medianIndex + 1, inputArrayLength);
merge (inputArray, startIndex, medianIndex, inputArrayLength);
}
}
The function mergeSort expects 3 parameters. The array to be sorted (int inputArray[]); the starting point of the array for the function call (int startIndex); and the length of the array (int inputArayLength). The length of the array represents the index of the last element (counting begins from 0).
This function implements Merge Sort algorithm in a recursive manner (note the function calls itself). The function first gets a suitable middle element to divide the list it is working with into two halves (equal, or almost equal; in the latter one list has one element more than the other).
The function then calls itself for the left half and the right half and then calls another function merge, to merge the two lists it worked on.
When calling itself recursively, mergeSort keeps dividing the list it works upon further, until the list reduces to unit size. Hence, the entire logic is wrapped under an if condition, which says that the function should do something only if the starting position of the array is less than the number of elements in the list, basically giving the control back to the previous recursive call upon encountering a single element sub-array.
void merge(int inputArray[], int startIndex, int medianIndex, int inputArrayLength)
{
int leftLoop, rightLoop, remainderLoop;
int leftArrayLength = medianIndex - startIndex + 1;
int rightArrayLength = inputArrayLength - medianIndex;
int leftArray[leftArrayLength], rightArray[rightArrayLength];
The function merge is the place where actual sorting of elements happen. The function sorts the elements by merging the two sub-arrays, comparing each element and putting them in their correct place when doing so. It is important to note, that the program is passing the address of main array, sortedNumberList since the beginning, hence the sub-lists are actually changing data elements in the main array itself. Let's look at it further.
The function merge accepts 4 arguments: int inputArray[] (the address of the array being worked upon), int startIndex (the index of the first element of the sub-list), int medianIndex (the index of the middle element of the sub-list), int inputArrayLength (the length of the sublist).
Additionally, we have a bunch of variables defined to aid in the process. int leftLoop, rightLoop, remainderLoop are the various loop variables. int leftArrayLength = medianIndex - startIndex + 1 stores the length of left sub-array and int rightArrayLength = inputArrayLength - medianIndex; stores the length of right sub-array. int leftArray[leftArrayLength], rightArray[rightArrayLength]; are the arrays that will hold the sublist data.
Left and right sub-arrays are then populated with the data, left of the median and right of the median.
Next, the while loop compares all the elements of both sub arrays and put them at appropriate positions. Whichever element is successfully put in place, should not be repeated in comparisons, hence the loop counter for that list is incremented. However, it is important to note that once either of the lists is empty, the remaining elements of the other list are left as-is. Hence, we have the other two while loops, that push in the remaining elements. Since the mergeSort function calls merge with lists as small as 2 elements, the remaining sub-list is always sorted. The remainderLoop variable is pointing to the element of main array that should be replaced. Hence, in the end when the control comes out of the merge function, the part of the list is sorted which it was working with.
The combination of mergeSort and merge calls, eventually sorts the entire array.
lengthNumberList = 0; -> This is the fourth case where we reset the lengthNumberList variable, which tracks the last element of the array. This helps in giving the user ability to redo any operation, without the need of closing and starting the program again.
printf ("Thank You for using SortingAlgorithms v1.3\n");
printf ("Made by Toxifier\n");
This is the fifth case statement, which allows the user to safely exit the program.
default:
printf ("\nWrong Choice!\n");
When using the case statement, it is important to use the break keyword at the end of each case to avoid the program from falling through the next case. It is also important to note the default case, which is important to handle any wrong values in the switch-case logic.
system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.
Write a recursive function to obtain the running sum of first 25 Natural Numbers.
Explanation of Problem
I have made a more general program that could handle most of the numbers in the integer limits. The user can obtain the desired output by inputting 25 to the program.
int recSumNat(int a)
{
if (a < 1)
return a;
else if (a == 1)
return 1;
else
return (a + recSumNat(a-1));
}
int main()
{
int number;
printf("\n\nEnter a number: ");
scanf("%d", &number);
printf("\n\nSum of Natural numbers upto %d: %d\n\n", number, recSumNat(number));
system("pause");
return 0;
}
Explanation of Code
#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H
int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.
printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.
scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.
if (a < 1)
return a; -> If the user enters an integer which is not a Natural Number, the program would return the number itself, since the program is trying to find the sum of natural numbers upto the number entered by the user, that is, first n natural numbers.
else if (a == 1)
return 1; -> As soon as the value of the 'a' argument becomes 1, the function returns 1.
else
return (a + recSumNat(a-1)); -> For any natural number other than 1, the function returns the sum of the current value of 'a' with the current call to the function, and the value returned by the function when called with 'a-1'. Thus, we are guaranteed to exit the recursive stack as soon as the value of 'a' reaches 1.
system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.
A positive integer is entered through the keyboard, write a function to find binary equivalent of this number using recursion.
Explanation of Problem
We need to design a recursive function that could find the binary equivalent of a positive integer. It is a simple program. All our function needs to do is print the (number modulus 2) at each iteration, while we keep feeding the next call with number/2.
Code
#include <stdio.h>
/**@Title: BinaryEquivalent Recursive.c*
*@Language: ANSI C*
*@Compiler: GNU GCC*
*@IDE: Code::Block 13.12*
*@Author: Toxifier*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 12-06-2014*
*/
void binaryEquiRec(long a)
{
if (a)
{
int num = a % 2;
binaryEquiRec(a / 2);
printf("%d", num);
}
}
int main()
{
long number;
printf("\n\nEnter a number: ");
scanf("%ld", &number);
printf("\nBinary equivalent of %ld is: ", number);
binaryEquiRec(number);
printf("\n\n");
system("pause");
return 0;
}
Explanation of Code
#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H
int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.
printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.
scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.
if (a) -> Since in each recursive call, we divide the number fed to the function by 2 (binaryEquiRec(a / 2);), this if condition guarantees that the function would return in case 'a' becomes zero, which would mean 'a / 2 = 0', which is rue iff 'a' is zero. I keep dividing the number by 2 in each call because since we use the statement, int num = a % 2; to set 'num' as 'a % 2', it means we should reject the current 2's multiple from the number to keep on going with our calculation (the current multiple has already contributed).
printf("%d", num); -> This statement is used to print the binary equivalent digit by digit. I have called this after the recursive call to get the number in correct order, else I would get the reverse of the binary equivalent. So what happens is that, as soon as the if condition fails, the last function call returns, that means the MSD of the binary equivalent is returned, which must be published as the leading bit.
system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.
Write a Recursive Function to obtain first 25 numbers of a Fibonacci Sequence. In a Fibonacci sequence, the sum of two successive terms gives the third term. Following are the first few terms of the Fibonacci Sequence:
1 1 2 3 5 8 13 21 34 55 89...
Explanation of Problem
The problem is simple enough and we just need to print the first 25 terms of the Fibonacci sequence using a recursive function. But I have written a rather general program which could generate the Fibonacci sequence upto nth term. All you need to do is, supply 25 as the input and you will get the first 25 terms.
int recFibo(int a1, int a2, int num)
{
if (num)
{
printf("%d ", a1);
return recFibo(a2, a1 + a2, num - 1);
}
return 0;
}
int main()
{
int number;
printf("\n\nEnter a number: ");
scanf("%d", &number);
recFibo(1, 1, number);
printf("\n\n");
system("pause");
return 0;
}
Explanation of Code
#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H
int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.
printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.
scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.
recFibo(1, 1, number); -> This is the call to the recursive function we have designed in this program. Just pass 25 as the value of the variable number to get the sequence upto 25 terms. Else he program is generalised to get results upto nth term (as long as the result is within the range of int, memory & computational power).
int recFibo(int a1, int a2, int num) -> The function that calculates the Fibonacci Sequence. It's input are two successive terms, a1 and a2 which are used to compute the next term. The variable num is the number of times we wish to call this function.
if (num) -> The statement makes sure that the block is executed only if the value of num is non zero. As soon as the value becomes zero, the block is not executed. Please note that on encounter of a negative number, we will get unfavourable results. The program is designed to handle positive int only. In case you wish to handle the negative number situation, you can use, if (num > 0).
printf("%d ", a1); -> Prints the first term. We could have also used a1 + a2, but then we will not able to produce 1 1 in the beginning. So while calling the function from main, if you rather use recFibo(0, 1, number);, then you can use, printf("%d ", a1 + a2); instead.
return recFibo(a2, a1 + a2, num - 1); -> This is the most important line in this program which makes recursive call to the function recFibo. Please note, we have supplied the second term, and third term of any three terms in sequence in this call. Also, we decrement num by 1 on each recursive call, so that our if condition gets violated at right time and the program terminates at the right time.
system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.
A positive integer is entered through the keyboard, write a program to obtain the prime factors of the number. Modify the function suitably to obtain the prime factors recursively.
Explanation of Problem
In this program, we need to devise a function that would find the prime factors of a number recursively.
void prime(int x)
{
int a; //loop counter
for( a = 2; a <= x; a++ )
{
if( x % a == 0 )
{
printf("%d ",a);
prime(x/a);
break;
}
}
}
int main()
{
int number;
printf("\n\nEnter a number: ");
scanf("%d", &number);
prime(number);
printf("\n\n");
system("pause");
return 0;
}
Explanation of Code
#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H
int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.
printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.
scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.
for( a = 2; a <= x; a++ )
{
if( x % a == 0 )
{
printf("%d ",a);
prime(x/a);
break;
}
}
This is the part of code where the calculation takes place. The for loop, for( a = 2; a <= x; a++ ) keeps incrementing the counter, 'a'. We use it to divide the number that user entered. The if condition, if( x % a == 0 ) checks if the number is divisible by the current value of the counter 'a'. If that is the case, we print the number 'a' and call our function prime recursively, but this time with a value 'x/a' rather than 'x'. With this, we are not stuck in an infinite recursion of printing the same prime factor. Since we keep on dividing the number by the prime factor found in last iteration, we are sure of segregating any multiples of this 'found prime factor'. Hence, we avoid getting the composite factors, since the counter always starts at 2. Thus only prime factors get printed on the screen, with a single space separating each of them.
system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.
A 5-digit positive integer is entered through the keyboard, write a function to calculate sum of digits of the 5-digit number:
(1) Without using recursion
(2) Using recursion
Explanation of Problem
We wish that the user enters a 5 digit number. We have to make 2 functions one of which will calculate the sum of digits normally, and other will use recursion to do the same.
int digSum(int number)
{
int sum = 0;
while (number)
{
sum += number % 10;
number /= 10;
}
return sum;
}
int digSumRec(int number)
{
if (number)
return (number % 10 + digSumRec(number / 10));
else
return 0;
}
int main()
{
int number, sum = 0;
printf("\n\nEnter a 5 digit number: ");
scanf("%d", &number);
printf("\nSum without recursion: %d\nSum with recursion: %d\n\n", digSum(number), digSumRec(number));
system("pause");
return 0;
}
Explanation of Code
#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H
int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.
printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.
scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.
int digSum(int number)
{
int sum = 0;
while (number)
{
sum += number % 10;
number /= 10;
}
return sum;
}
This is the first function that calculates the sum of digits normally. main() calls this functions with the user entered number as the argument. Inside the function, I have devised a while loop. Why have I used 'number' in the condition? Since I will extract the last digit and add it to the running sum into the variable 'sum', and also divide the number by 10 in each iteration. Once the number turns to be 0 on continuous dividing, the control comes out of the loop, and 'sum' is returned.
int digSumRec(int number)
{
if (number)
return (number % 10 + digSumRec(number / 10));
else
return 0;
}
This is our recursive function. In this case, we do the same thing as above, but instead of while loop, we achieve the same thing using recursion. The if condition is similar to the while loop block in the former function. The statement which executes when the 'if' block condition is true, calls the function digSumRec recursively, but the argument is passed as number / 10 instead of number. Thus as soon as number / 10 returns zero, the if block is not executed. Moreover, the return statement in the if block does the addition part. It extracts the last digit from the 'number' and adds to it what is returned by the recursive call to the procedure.
system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.
+-+C+Program.png)
