Is my understanding of CS50 Lab 5: Inheritance correct?

So I'd like if someone could tell me if my understanding of the Inheritance problem from Week 5 is correct or not.

// Simulate genetic inheritance of blood type

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Each person has two parents and two alleles
typedef struct person
{
    struct person *parents[2];
    char alleles[2];
}
person;

const int GENERATIONS = 3;
const int INDENT_LENGTH = 4;

person *create_family(int generations);
void print_family(person *p, int generation);
void free_family(person *p);
char random_allele();

int main(void)
{
    // Seed random number generator
    srand(time(0));

    // Create a new family with three generations
    person *p = create_family(GENERATIONS);

    // Print family tree of blood types
    print_family(p, 0);

    // Free memory
    free_family(p);
}

// Create a new individual with `generations`
person *create_family(int generations)
{
    // TODO: Allocate memory for new person
    person *p = malloc(sizeof(person));

    // If there are still generations left to create
    if (generations > 1)
    {
        // Create two new parents for current person by recursively calling create_family
        person *parent0 = create_family(generations - 1);
        person *parent1 = create_family(generations - 1);

        // TODO: Set parent pointers for current person
        p->parents[0] = parent0;
        p->parents[1] = parent1;

        // TODO: Randomly assign current person's alleles based on the alleles of their parents
        p->alleles[0] = parent0->alleles[rand() % 2];
        p->alleles[1] = parent1->alleles[rand() % 2];

    }

    // If there are no generations left to create
    else
    {
        // TODO: Set parent pointers to NULL
        p->parents[0] = NULL;
        p->parents[1] = NULL;

        // TODO: Randomly assign alleles
        p->alleles[0] = random_allele();
        p->alleles[1] = random_allele();
    }

    // TODO: Return newly created person
    return p;
}

// Free `p` and all ancestors of `p`.
void free_family(person *p)
{
    // TODO: Handle base case
    if (p == NULL)
    {
        return;
    }

    // TODO: Free parents recursively
    free_family(p->parents[0]);
    free_family(p->parents[1]);

    // TODO: Free child
    free(p);
}

// Print each family member and their alleles.
void print_family(person *p, int generation)
{
    // Handle base case
    if (p == NULL)
    {
        return;
    }

    // Print indentation
    for (int i = 0; i < generation * INDENT_LENGTH; i++)
    {
        printf(" ");
    }

    // Print person
    if (generation == 0)
    {
        printf("Child (Generation %i): blood type %c%c\n", generation, p->alleles[0], p->alleles[1]);
    }
    else if (generation == 1)
    {
        printf("Parent (Generation %i): blood type %c%c\n", generation, p->alleles[0], p->alleles[1]);
    }
    else
    {
        for (int i = 0; i < generation - 2; i++)
        {
            printf("Great-");
        }
        printf("Grandparent (Generation %i): blood type %c%c\n", generation, p->alleles[0], p->alleles[1]);
    }

    // Print parents of current generation
    print_family(p->parents[0], generation + 1);
    print_family(p->parents[1], generation + 1);
}

// Randomly chooses a blood type allele.
char random_allele()
{
    int r = rand() % 3;
    if (r == 0)
    {
        return 'A';
    }
    else if (r == 1)
    {
        return 'B';
    }
    else
    {
        return 'O';
    }
}

So we start by allocating space for the individual. My question here is...how much space does the computer allocate? The person structure has 2 parent persons, which will have their own parents and so on and so forth. So how does the computer know how much space to allocate?

After allocating space for the person, we start recursively calling the function for each generation. So let's name them as the individual, P[A], P[B], GP[A] and GP[B], where P -> Parent, and GP -> Grandparent and A and B mean first and second respectively.

So we first go into the loop for P[A]. We ask the computer to allocate space again. But we use the same variable p to point to a new block of memory for P[A]. Won't that result in the block of memory we allocated for the individual being lost? Then we call the function for the grandparents of P[A], i.e. GP[A] and GP[B]. We first go into GP[A], and since generation is < 1, we set its parent pointers to null and give it random alleles. Same for GP[B].

After both calls of the function are done for P[A], we then set the parents array of P[A] to be equal to the pointers, parent0 and parent1, which point to GP[A] and GP[B] respectively.

Then we do the same for P[B].

Then we do the same for the individual and we move on to the next function, free_family.

In free_family, do we end up calling the function for the parents of each grandparent as well? Cuz then it makes sense that the function returns and we end up freeing the child, which in this case is the grandparent. And then we do the same for each grandparent, which results in the parents being freed. And then finally we free the individual.

So is my explanation correct. Do you have any explanations for my questions that I have highlighted in bold? Would greatly appreciate any advice.

> So we start by allocating space for the individual. My question here is...how much space does the computer allocate? The person structure has 2 parent persons, which will have their own parents and so on and so forth. So how does the computer know how much space to allocate?

You are mixing up the semantic interpretation of your data types with their actual structure, and perhaps also getting confused about indirection. Like every C struct (that does not have a flexible array member), your struct person has a fixed, definite size. You can, for example, determine this size via the sizeof operator. It will be at least large enough to accommodate all the members, which are

• an array of two pointers to struct person
• an array of two char

On a typical implementation featuring 64-bit pointers, I would expect such a structure to be 24 bytes in size -- 16 for the two pointers, two for the two chars, and 6 bytes of padding for alignment purposes. Implementations may choose differently, but whatever that size is, that's how many bytes malloc(sizeof(person)) will attempt to allocate.

And note well that one struct person does not contain others. C does not permit a structure type to directly or indirectly contain sub-objects of its own type. But it does permit structures to contain pointers to other objects of the same type, which is what you have.

> So we first go into the loop for P[A]. We ask the computer to allocate space again. But we use the same variable p to point to a new block of memory for P[A]. Won't that result in the block of memory we allocated for the individual being lost? Then we call the function for the grandparents of P[A], i.e. GP[A] and GP[B]. We first go into GP[A], and since generation is < 1, we set its parent pointers to null and give it random alleles. Same for GP[B].

I don't see any such loop in the program. Unless the question is hypothetical (in which case the answer depends on many details that have not been presented), I think you must be talking about the create_family function, which does not loop, but does recurse.

Here you need to understand that among the key properties of functions is that each execution of any function gets its own set of non-static local variables. Including when it calls itself recursively. So the p in the initial call to create_family is a different variable from the p used in each of its recursive calls to create_family, and each of those calls' own recursive calls get their own ps, etc.. These are all independent; one does not clobber another.

> In free_family, do we end up calling the function for the parents of each grandparent as well? Cuz then it makes sense that the function returns and we end up freeing the child, which in this case is the grandparent. And then we do the same for each grandparent, which results in the parents being freed. And then finally we free the individual.

Yes. free_family frees the parents of each person by recursively calling itself. So in those recursive calls, it frees the parents' parents. And in those calls, the parents' parents' parents, up to the point in each branch where the person's parents are not recorded (as indicated by null pointers).

> So I'd like if someone could tell me if my understanding of the Inheritance problem from Week 5 is correct or not.

It's a confusing name since Inheritance is a separate CS concept, but doesn't apply to C anyway. What you're really learning here is the concepts behind recursive functions, and while I didn't debug / execute / compile, conceptually you are asking the correct questions.

> how does the computer know how much space to allocate?

Since you call create_family recursively, the compiler doesn't have to compute how much space beforehand. It can simply run each malloc in order and the correct amount of space is allocated. The computer just allocates as it goes, it doesn't need to know how much total at any time.

> we use the same variable p

Variable p is scoped to a particular invocation of create_family. Each time you call create_family it gets its own p.

> In free_family, do we end up calling the function for the parents of each grandparent as well?

free_family is also recursive. It calls free_family on each parent. But then for each parent, it calls free_family for each of the parent's parents. And for each grandparent, it calls free_family for each of those parents. So yes, every generation that was allocated with the recursive create_family will also be deallocated when you call free_family.

Not to answer your questions, but as a side note: a simpler way to solve this is the example given by Wikipedia. A (simplified) ancestry chart is an example of a perfect binary tree. The generations, k, leads to a fixed number of persons (nodes), n = 2^(k+1) - 1. In tree terminology, the parent has two children; in a genealogy tree, it is the other way around: two parents produce a child.

This allows us to store the data structure in a fixed packed array as an automatic variable on the heap using index i, 2i+1 and 2i+2 as parents (in tree terminology, children) and (i-1)/2 as the child (in tree terminology, parent). We work backwards in the array. The number of top ancestors without record of previous ancestry corresponds to the leaf nodes, of which there are l = (n + 1)/2.

#include <stdlib.h> /* Includes stddef. */
#include <stdio.h>
#include <time.h>
#define GENERATIONS 3
#define NODES ((2 << (GENERATIONS + 1)) - 1)
#define LEAVES ((NODES + 1) / 2)
/* X-Macro allows parallel assignment of enum and strings with one source. */
#define ALLELES X(A), X(B), X(O)
#define X(a) a
enum allele { ALLELES };
#undef X
#define X(a) #a
static const char *const alleles[] = { ALLELES };
#undef X
#undef ALLELES
static const size_t alleles_size = sizeof alleles / sizeof *alleles;
/** Two enums is overkill for only 9 combinations, but convenient. */
struct person { enum allele allele[2]; };
int main(void) {
/* An (idealized) family tree is a perfect binary tree
<https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees>. */
struct person family[NODES];
size_t i;
srand((unsigned)clock()); /* Seed. */
printf("digraph {\n"
"\tgraph [truecolor=true, bgcolor=transparent, fontname=modern];\n"
"\tnode [shape=none, fontname=modern];\n"
"\n"
"\t// leaves; ancestor nodes\n");
for(i = LEAVES - 1; i < NODES; i++) {
struct person *const leaf = family + i;
leaf->allele[0] = (unsigned)rand() / (RAND_MAX / alleles_size + 1);
leaf->allele[1] = (unsigned)rand() / (RAND_MAX / alleles_size + 1);
printf("\tnode%zu [label = \"%s%s\"];\n",
i, alleles[leaf->allele[0]], alleles[leaf->allele[1]]);
}
printf("\n"
"\t// branches; backwards\n");
i = LEAVES - 1; do {
/* https://en.wikipedia.org/wiki/Binary_tree#Arrays */
const size_t p = 2 * --i + 1;
const struct person *const parents = family + p;
struct person *const branch = family + i;
branch->allele[0] = parents[0].allele[rand() > RAND_MAX / 2];
branch->allele[1] = parents[1].allele[rand() > RAND_MAX / 2];
printf("\tnode%zu [label = \"%s%s\"];\n"
"\tnode%zu -> node%zu;\n"
"\tnode%zu -> node%zu;\n",
i, alleles[branch->allele[0]], alleles[branch->allele[1]],
p, i, p + 1, i);
} while(i);
printf("}\n");
return EXIT_SUCCESS;
}

Sample output piped though GraphViz: