CODEWITHSUNDEEP
cmemory-leaks
user1000
user1000

Reputation: 91

Is there a memory leak in this C code?

In

https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

the C implementation calls malloc inside the recursive function. Isn't that a memory leak?

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

int mod (int a, int b){
    return a %b; 
}   

int *extendedEuclid (int a, int b){
   int *dxy = (int *)malloc(sizeof(int) *3);

   if (b ==0){
      dxy[0] =a; dxy[1] =1; dxy[2] =0;

       return dxy;
   }
   else{
       int t, t2;
       dxy = extendedEuclid(b, mod(a, b));
       t =dxy[1];
       t2 =dxy[2];
       dxy[1] =dxy[2];
       dxy[2] = t - a/b *t2;

       return dxy;
    }
}

int main(void)
{
   int a =99, b =78;
   int *ptr;

   ptr =extendedEuclid (a, b);
   printf("%d = %d * %d + %d * %d \n",ptr[0], a, ptr[1], b, ptr[2] );

   return 0;        
}

How do you free memory allocated in recursive functions?

Upvotes: 1

Views: 126

Answers (2)

klutt
klutt

Reputation: 31389

Isn't that a memory leak?

Yes it is. An easy method to see this is the program valgrind

$ valgrind ./a.out 
==8528== Memcheck, a memory error detector
==8528== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==8528== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==8528== Command: ./a.out
==8528== 
3 = 99 * -11 + 78 * 14 
==8528== 
==8528== HEAP SUMMARY:
==8528==     in use at exit: 72 bytes in 6 blocks
==8528==   total heap usage: 7 allocs, 1 frees, 1,096 bytes allocated
==8528== 
==8528== LEAK SUMMARY:
==8528==    definitely lost: 72 bytes in 6 blocks
==8528==    indirectly lost: 0 bytes in 0 blocks
==8528==      possibly lost: 0 bytes in 0 blocks
==8528==    still reachable: 0 bytes in 0 blocks
==8528==         suppressed: 0 bytes in 0 blocks
==8528== Rerun with --leak-check=full to see details of leaked memory
==8528== 
==8528== For counts of detected and suppressed errors, rerun with: -v
==8528== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

How do you free memory allocated in recursive functions?

Hard to give a general answer to that question. It depends on the specific function. In this specific case you could change it so that you write the result to an output parameter instead of returning a pointer. Then the prototype of your method could look like this:

void extendedEuclid (int a, int b, int *dxy)

Remove the line declaring dxy and the malloc call, change extendedEuclid(b, mod(a, b)) to extendedEuclid(b, mod(a, b), dxy) and remove the return statements. Then, in main you do this:

int *ptr = malloc(sizeof(int) *3);
extendedEuclid (a, b, ptr);
printf("%d = %d * %d + %d * %d \n",ptr[0], a, ptr[1], b, ptr[2] );
free(ptr);

Oh, and don't cast malloc

Upvotes: 0

4386427
4386427

Reputation: 44274

Isn't that a memory leak?

Yes, it is. Every time a recursive call is made, i.e. here:

dxy = extendedEuclid(b, mod(a, b));

the just malloc'ed memory is leaked as dxy is overwritten with a new value (aka the return value)

The code should be more like:

int *extendedEuclid (int a, int b){
    int *dxy;
    if (b ==0){
        dxy = (int *)malloc(sizeof(int) *3);  // Move malloc to here
        dxy[0] =a; dxy[1] =1; dxy[2] =0;

        return dxy;
    }
    else { ....

So that the malloc is only done once, i.e. when there is no recursive call

Upvotes: 3

Related Questions