Can I free mallocs that are being generated in every step of a recursion in C?

Viewed 70

I am making a simulation with C (for perfomance) that (currently) uses recursion and mallocs (generated in every step of the recursion). The problem is that I am not being able to free the mallocs anywhere in the code, without having the wrong final output. The code consist of two functions and the main function:

evolution(double initial_energy)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

double * evolution(double initial_energy){
    
    double * energy_vec = malloc(sizeof(double)*50);
    for(int i = 0; i <= 50; i++){

        energy_vec[i] = 0;

    }

    int i = 0;

    while(initial_energy > 1){

        initial_energy /= 2;
        energy_vec[i] = initial_energy;
        i++;
    }
    return energy_vec;
}

here is where mallocs are generated. Then I define recursion(double initial_energy) that return the total number of events, being events the times that the initial_energy is divided by 2 until its value is less than 1.

double recursion(double initial_energy){

    int event_counter = 0;
    int j = 0;
    double * Energy;

    Energy = evolution(initial_energy);

    while(Energy[j] > 0.0){

        event_counter++;
        event_counter += recursion(Energy[j]);
        j++;
    }
    return event_counter;
}

and finally the main function, that here doesn't make much a difference to have it, but for the sake of completeness here it is

int main(){

    int trials = 20000;
    int events;
    double initial_energy = 70;

    for(int i = 0; i <= trials; i++){

        events = recursion(initial_energy);
        printf("%i) events = %i\n",i, events);
        usleep(200);
    }
    return events;
}

So, is it possible for this code, to free the mallocs anywhere and have the correct result at the end? (The correct result should be 2**N - 1, where N is the number of times a value greater than 1 can result from dividing initial_energy by 2 successivelly. For example, for this code, the correct answer would be 127 at the end of the program). I have tried defining the malloc inside the for loop in the main function, and freeing it right after I call recursion, but it doesn't hold the correct result.

I only use C ocassionally (when python performance is too slow for some sort of calculations), so I do not have the technical understanding of the language that I would like. So I am open to whatever changes in the code are necessary.

Thanks in advance!

2 Answers

You're supposed to free memory right after the last time it will be used. In your program, after the while loop in recursion, Energy isn't used again, so you should free it right after that (i.e., right before return event_counter;).

Joseph Sible-Reinstate Monica is correct about the question you asked. But your code can be improved in a number of areas. If you want to see the final version, you should scroll all the way to the bottom of my answer for run_simulation, which is a dramatically better version of your recursion function.

Let's start with your initial function, evolution. If you want to allocate memory and initialize all bytes to 0, you should use the calloc function rather than malloc. Instead of

double * energy_vec = malloc(sizeof(double)*50);
for(int i = 0; i < 50; i++){ // your original i <= 50 was wrong
    energy_vec[i] = 0;
}

you should instead do

double * energy_vec = calloc(50 * sizeof(double));

This is usually more efficient than malloc + manually setting everything to 0, and it's more readable.

Second, there is no reason for recursion to return a double except. The most logical thing for recursion to return would be an unsigned int, since it will always return a nonnegative integer. This is practically a drop-in replacement; just change the return type and the type of event_counter to unsigned int, and your code will work just fine without pointlessly returning a double. I will make this switch - for now.

Third, a double can be larger than 2^50. In the event that this happens, your energy array isn't going to be big enough. This is a serious problem, but it could be averted by dynamically resizing the array. A higher-level high-performance language like Rust or C++ would provide you with resizable arrays as part of the standard library, but in C, you'd have to do it by hand.

Fourth, you in fact do not need dynamic memory allocation at all because your code can be done with mathematics. You can actually get away with not having loops at all! However, to avoid using "floating point black magic", I will use loops in my answer. We first define

unsigned int count_divisions(double d) {
    unsigned int count;
    for (count = 0; d > 1.0; d /= 2, count++);
    return count;
}

Note that count_divisions(d) is exactly equal to the conceptual length of evolution(d).

Now, we should note that the only properties we actually care about for our Doubles is there count_divisions value. It's the only thing we use. Thus, everywhere I see a double, I will replace it with its count_divisions value. The resulting code looks like this:

unsigned int * evolution(unsigned int divisions){
    unsigned int * Energy = malloc(divisions * sizeof(*Energy));
    for(unsigned int i = 0; i < divisions; i++) {
        Energy[i] = divisions - i - 1;
    }
    return Energy;
}

unsigned int recursion(unsigned int divisions) {
    unsigned int* energy_vec = evolution(divisions);
    unsigned int count = divisions;
    for (unsigned int j = 0; j < divisions; j++) {
        count += recursion(energy_vec[j]);
    }
    free(energy_vec);
    return count;
}

Now, we're beginning to approach the answer. But notice that we actually already know what energy_vec[j] is for each j; it will be divisions - j - 1. So we can completely eliminate the energy_vec vector and get the following code:

unsigned int recursion(unsigned int divisions) {
    unsigned int* energy_vec = evolution(divisions);
    unsigned int count = divisions;
    for (unsigned int j = 0; j < divisions; j++) {
        count += recursion(divisions - j - 1);
    }
    return count;
}

which we can trivially rewrite as

unsigned int recursion(unsigned int divisions) {
    unsigned int* energy_vec = evolution(divisions);
    unsigned int count = 0;
    for (unsigned int j = 0; j < divisions; j++) {
        count += recursion(j);
    }
    return count + divisions;
}

Now, we must use a bit of cleverness to deduce a better recurrence relation for recursion. It turns out that it is possible to show that recursion(0) = 0 and that recursion(k + 1) = 2 * recursion(k) + 1. This is because

recursion(k + 1) 
= recursion(0) + recursion(1) + ... + recursion(k) + k + 1
= (recursion(0) + recursion(1) + ... + recursion(k - 1) + k) + recursion(k) + 1
= recursion(k) + recursion(k) + 1
= 2 * recursion(k) + 1

Therefore, we can easily prove by induction that recursion(k) = 2^k - 1.

So in fact, you're taking in the value initial_energy and returning 2^(ceil(log(initial_energy))) - 1.

A final solution could thus be

double run_simulation(double initial_energy) {
    double power_of_two = 1;
    while (initial_energy > 1) {
        power_of_two *= 2;
        initial_energy /= 2;
    }
    return power_of_two - 1;
}

which replaces your original recursion function at much less cost.

Related