The first concept I’m learning about today is different kinds of sorting algorithms, namely selection sort and bubble sort. The examples that demonstrated these algorithms consisted solely of numbers, so it’s pretty low level, but unobfuscated how a computer might go about the process of organizing an unorganized list of information.
The concept of n - 1 and lower bounds / higher bounds have also been helpful in understanding the concept of binary organization. For instance, the computer reiterates the function of n - 1 in the case of selection sort and n - 2 in the case of bubble sort, the latter being simply to ‘do’ (n - 1) things (n - 1) times, in order to sequence an array of numbers from higher to lower. While it is a low-level concept, it is still helpful to understand the way in which these processes work. At this point, any information that I have not yet been exposed to is helpful.
Now I’m going to explore the concept of recursion, where a component(?) of a function calls back to—or literally points to—itself later on in a function. This concept is seen in chemistry, mathematics, and in over aspects of the real world: such as the variable ‘f’ at both the beginning and the end of a given arithmetical expression.
Time to make a program that helps me understand recursion more.
In this program, we are going to declare a function at the top of the code, called draw. Then, we ask the user for the height, which we will use to create a pyramid out of hash(#) symbols. The for (int i = 0; i < n; i++) creates and controls the number of rows, and the for (int j = 0; j < i + 1; j++) line will control the number of hash(#) symbols. Then the print(“#”); line prints the ‘blocks’ of the pyramid, with the ultimate line printf(“\n”); printing a newline character which starts a new row after each row of hashes, thus giving the pyramid its vertical structure.
#include <cs50.h>
#include <stdio.h>
void draw(int n);
int main(void)
{
int height = get_int("Height: ");
draw(height);
}
void draw(int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i + 1; j++)
{
printf("#");
}
printf("\n");
}
}
However, if you notice, this program doesn’t use recursion, so I’m going to remake the program with a recursive function so that we can see the difference.
#include <cs50.h>
#include <stdio.h>
void draw(int n);
int main(void)
{
int height = get_int("Height ");
draw(height);
}
void draw(int n)
{
if (n <= 0)
{
return;
}
draw(n - 1);
for (int i = 0; i < n; i++)
{
printf("#");
}
printf("\n");
}
Now, you can see that we’ve declared and then used draw to draw the pyramid from top to bottom, and each time the statement draw(n - 1) is used, it calls back to itself to draw a smaller pyramid until it reaches the height of 0. This prevents the recursive function from running infinitely and causing a stack overflow, as we have provided the program with a condition that prevents it from running past 0.
So, as far as I understand, using the recursive function versus the loop doesn’t necessarily make the program better, since they’re both valid and both produce the same output. But it does break down problems into smaller problems that can produce more readable code, so there’s that.
Merge Sort
Speaking of breaking problems into chunks and solving them that way, I’ve just been introduced to merge sorting, which is a recursive way of sorting information by breaking down the unsorted (input) into sorted (output) by means of sorting left and right halves, and then the left and right halves of those left and right halves until the array as a whole is sorted. Just as when I was exploring selection sort and bubble sort, this was done with an array of 8: 0,1,2,3,4,5,6,7.
x—x
That’s all for this post! Thanks for reading.