-   Programming (
-   -   Freeing dynamically allocated memory in a C recursive function (

marian57 09-11-2011 02:42 AM

Freeing dynamically allocated memory in a C recursive function
Hi! all
I have a problem in a C program; it crashes while on 'free()' inside a recursive function, the message being that it cannot find a pointer on the heap.
It computes factorial numbers of biiig length using strings of digits rather than numeric variables. Because I could not find the bug, I modified the program so that I can use a loop instead than recursion if I choose to do so; well the problem disappears, using a loop, and the rest of the code (doing 'N * (N - 1) etc.) remains the same.
In recursive mode there is some kind of overflow, I can see it using 'printf()' but am not able to fix it, and all that the recursive function does is allocating memory to accommodate 'N -1' N - 1 times then copies 'N' to that memory, calls a function to do the actual '- 1' operation, and calls a 'multiplication' function which returns the partial result. Exactly the same thing, using the same functions happens in the 'loopit()' function; the only difference is that in this case I can normally free the allocate memory.
In the 'multiplication' function 'realloc()' is called when needed, ad that seems to be part of the bug, but that (exactly the same) is done in either modes, and when linked to '-ldmalloc' all memory results as freed in 'loop' mode, but "free()' is crashing in 'recurse' mode.
The only way I am able to get it to work in recursive mode is by calculating the total number of digits in the eventual factorial, then
allocating that length + 2 to the 'number' string in 'main()', and passing the size as a pointer to the other functions; that way 'realloc()' needs not be called, but it involves calculating the number o digits before hand.
So probably 'realloc()' is the problem, but it is called extensively in 'loop' mode without problems.
I'm attaching the source, but this version cannot do the job explained above (number of digits in advance), so it crashes in 'recurse' mode on big numbers.
Thank you for having read all this, and some suggestions would be appreciated.
Regards marian57

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

#ifdef DMALLOC
#include <dmalloc.h>

#define MESS "Usage:\n\
<prog> [-h]|[-l <num1> [<num2>]]\n\
Computes the factorial of 'num1', or multiplies 'num1' by 'num2'.\n\
-h - Print this\n\
-l - Compute the factorial of 'num1' using a loop, rather than recursion."

int NOREC = 0;

char *loopit(char *nu, int *sz);
char *fact(char *n, int *sz);
char *mulstr(char *st1, char *st2, int *s);
char *subone(char *sb);
char *reverse(char *rv);

/* ************************************************************************ */
int main(int argc, char **argv) {
int l = 0, i, num1 = -1, num2 = -1;
for(i = 1; i < argc; i++) {
if(!strcmp(argv[i], "-h")) {
return 0;
else if(!strcmp(argv[i], "-l"))
NOREC = 1;
else if(isdigit(*argv[i])) {
if(num1 == -1)
num1 = atoi(argv[i]);
else if(num2 == -1)
num2 = atoi(argv[i]);
else {
puts("\aMaximum 2 numbers.");
else {
puts("\aInvalid argument.");
if(num1 == -1 && num2 == -1)
puts("\a\nWe need a number.");
else if(num1 > -1 && num2 > -1) {
int sz = 16;
char *m1 = malloc(sz), *m2 = malloc(sz);
if(!m1 || !m2) {
perror("Allocation m1/m2");
sprintf(m1, "%d", num1);
sprintf(m2, "%d", num2);
m1 = mulstr(m1, m2, &sz);
printf("%d * %d =\n %s\n", num1, num2, m1);
else {
int num = num1;
for(;;) {
if(!*argv[1]) {
puts("\n<Enter> another number.");
scanf("%d", &num);
if(num < 0)
return 0;
while(getchar() != '\n');
int s = 16; /* The size which will grow to the eventual length of n1!. */
char *n1 = malloc(s);
sprintf(n1, "%d", num);
n1 = loopit(n1, &s);
n1 = fact(n1, &s);
l = strlen(n1);
printf("%d! = %s\nused %d bytes\nis %d digits long.\n", num, n1, s, l);
argv[1] = "";
num = -1;
return 0;

/* Computes N! usinf a loop. */
/* ************************************************************************ */
char *loopit(char *nu, int *sz) {
char *snu = malloc(strlen(nu) + 1);
if(!snu) {
perror("Allocation snu");
strcpy(snu, nu);
while(strcmp(snu, "1")) {
*sz = strlen(nu) + 1;
snu = subone(snu);
if(!strcmp(snu, "1"))
nu = mulstr(nu, snu, sz);
return nu;

/* Recursively computes N! in the form of string f. */
/* ************************************************************************ */
char *fact(char *f, int *s) {
if(!strcmp(f, "1") || !strcmp(f, "0"))
strcpy(f, "1");
else {
char *mone = malloc(strlen(f) + *s + 10);
if(!mone) {
perror("Allocation mone");
strcpy(mone, f);
mone = subone(mone);
if(f && *f && mone && *mone) {
if(strcmp(mone, "1"))
f = mulstr(f, fact(mone, s), s);
else {
printf("ERROR\a empty string.\n");
return f;

/* Multiplies a * b in the form of strings st1 and st2. */
/* ************************************************************************ */
char *mulstr(char *st1, char *st2, int *s) {
char *m1 = st1, *m2 = st2, *p1 = NULL, *p2 = NULL;
char **lines = NULL;
char *swap = NULL;
int i, j, k, l2 = 0, l1 = 0, cr;
if(strlen(st1) < strlen(st2)) {
m1 = st2;
m2 = st1; /* Pointer to the short string */
l2 = strlen(m2);
l1 = strlen(m1);
if((lines = (char**)malloc(sizeof(char*) * l2)) == NULL) {
perror("Allocation lines 0");
for(i = 0; i < l2; i++) {
if((lines[i] = (char*)malloc(l1 + l2 + 2)) == NULL) {
perror("Allocation 1");
p2 = m2 + l2 - 1;
i = 0;
cr = 0;
while(p2 >= m2) {
int n2 = *p2 - 48, n5 = 0;
j = 0;
p1 = m1 + l1 - 1;
cr = 0;
while(p1 >= m1) {
int n1 = *p1 - 48, n3 = n1 * n2 + cr, n4 = n3 / 10;
n5 = n3 % 10;
lines[i][j++] = n5 + 48;
cr = n4;
lines[i][j++] = cr + 48;
lines[i][j] = 0;
for(k = i; k < l2 - 1; k++)
strcat(lines[i], "0");
lines[i] = reverse(lines[i]);
for(k = 0; k < i; k++)
strcat(lines[i], "0");
if(*s < l1 + l2 + 2) {
*s = l1 + l2 + 2;
if((st1 = (char*)realloc(st1, *s)) == NULL) {
perror("Allocation st1 re");
memset(st1, 48, l1 + l2 + 2);
*(st1 + l1 + l2 + 1) = 0;
cr = 0;
for(k = l1 + l2 - 1; k >= 0; k--) {
int dtot = 0, d1, d2;
for(i = 0; i < l2; i++)
dtot += (lines[i][k] - 48);
dtot += cr;
d1 = dtot / 10;
d2 = dtot % 10;
cr = d1;
st1[k + 1] = d2 + 48;
st1[0] = cr + 48;
st1[l1 + l2 + 1] = 0;
if((swap = (char*)malloc(*s)) == NULL) {
perror("Allocation swap");
strcpy(swap, st1);
while(*swap && *swap == '0')
memmove(swap, swap + 1, strlen(swap));
strcpy(st1, swap);
for(i = 0; i < l2; i++)
return st1;

/* Reverses a string of digits. */
/* ************************************************************************ */
char *reverse(char *rv) {
int ln = strlen(rv);
char *p = rv + ln - 1, *tmp = alloca(ln + 1);
int j = 0;
if(!tmp) {
perror("Allocation tmp");
while(p >= rv) {
*(tmp + j++) = *p;
*(tmp + j) = 0;
strcpy(rv, tmp);
return rv;

/* 'subtracts' 1 from a string of digits. */
/* ************************************************************************ */
char *subone(char *sb) {
int nm = atoi(sb) -1;
sprintf(sb, "%d", nm);
return sb;

paulsm4 09-11-2011 03:51 AM

Hi -

1. Please use code tags. Here is the offending module:

char *
subone(char *sb) {
  char *p = sb + strlen(sb) - 1;
  char *swap = alloca(strlen(sb) + 1);
  while(p >= sb) {
    int dig = *p - 48;
    if(dig > 0) {
      *p = dig + 47;
    *p = 57;
  strcpy(swap, sb);
  while(*swap && *swap == '0')
    memmove(swap, swap + 1, strlen(swap));
  strcpy(sb, swap);
  return sb;

2. The positive comments:
a) You're calling malloc() and alloca() with "strlen()+1" - good!

b) You're pairing "free()" with "malloc()" in "loopit()", etc - good!

3. I'm frankly not sure what's wrong with "subone(char *sb)". But with all due respect, I would encourage you to simply re-write it. Think of what you're TRYING to do ... and do it differently. Simpler. K.I.S.S.


marian57 09-11-2011 06:39 AM

Thank you K.I.S.S.
That function was very silly; I was thinking in term of looong strings, but that string could not grow longer than 100000 or so or it would take a lifetime to compute.
However the bug is still there; I thought I had been a bit too lucky to get an answer so quickly.
Regards marian57

johnsfine 09-11-2011 09:09 AM

Skimming through the code from the top, the first bug I spotted was

f = mulstr(f, fact(mone, s), s);

When you call fact(mone,s) that can realloc the buffer pointed to by mone. So the subsequent free(mone) corrupts the memory pool.

So I think you wanted:


mone = fact(mone, s);
f = mulstr(f, mone, s);


Originally Posted by paulsm4 (Post 4468676)
Here is the offending module:

Wrong. The location of the symptom of a bug is just the location of the symptom of the bug, not necessarily the location of the bug.

Backtracking from the symptom of this kind of bug to the cause takes a lot of knowledge and patience in the debugger, and usually isn't required. That's why I skimmed through the code looking for the bug instead of even trying a debugger.

"Fixing" the code around the symptom (as you apparently convinced marian57 to try) is an even worse choice. (It drives me nuts every time programmers working with or for me make that mistake). At best, that accomplishes nothing (as it did for marian57 this time). More often, it moves the symptom around and adds to the confusion and causes you to add more bugs or leave bugs in the final product that you should have resolved.


Originally Posted by marian57 (Post 4468760)
I thought I had been a bit too lucky to get an answer so quickly.

I think it is still very quick. But maybe it could have been quicker.

I don't know who might have looked at your initial question before I did who might have noticed the bug if you had formatted the question properly (code tags and proper indentation on the code and better paragraph structure and white space on the question).

Maybe paulsm4 would have spotted the bug, instead of testing the code, if it had been properly indented. The important part of your code is very tiny. Only the lack of indenting makes the important parts hard to spot making the bug harder to spot.

Because of the bad formatting, I skipped your post the first time I noticed it. I was bored and came back to it an hour later. So if a better formatted post didn't get you an answer much earlier from someone else, it would at least have gotten you my answer an hour earlier.

paulsm4 09-11-2011 02:01 PM

@johnsfine -

I didn't "test" the code; I just glanced at it, satisfied myself that that a few of the most common errors (malloc (strlen), or multiple free's) were NOT the problem, and tried to politely suggest to the OP that "subone" was "sub-optimal".

I DIDN'T notice that "fact()" was playing games with "mone". Mea culpa.

But johnsfine, please get get the heck off your high horse and stop being such a condescending twit. OK?

johnsfine 09-11-2011 02:25 PM


Originally Posted by paulsm4 (Post 4469010)
I didn't "test" the code; I just glanced at it, satisfied myself that that a few of the most common errors (malloc (strlen), or multiple free's) were NOT the problem, and tried to politely suggest to the OP that "subone" was "sub-optimal".

I completely misunderstood your "Here is the offending module". Forums tend toward that kind of miscommunication. The OP apparently reacted to something in your post, motivating focus on that sub optimal function with the misguided belief that effort was toward correcting the bug. I stand by my stated viewpoint that such efforts are a counter productive response to unstable bugs.


I DIDN'T notice that "fact()" was playing games with "mone". Mea culpa.
I understand that as saying you understood something in my post as saying you are somehow at fault for not noticing the bug. One of us is misunderstanding: I said nothing to imply you were at fault for not noticing the bug, and I clearly said the opposite. The bad formatting of the original post was responsible for some delay in someone noticing the bug.

As for the rest of your post, I don't think a direct reply would be constructive.

ta0kira 09-11-2011 02:57 PM

That seems like a whole lot of code for what it does. My suggestion is to start over. If you're going with the same algorithm, at least break your procedures up into smaller ones.
Kevin Barry

marian57 09-11-2011 07:58 PM

Thanks johnsfine for showing me the bug
Thanks all of you
I'm only a retired boilermaker, who has picked up a bit of C on the web.
What I wanted to do there (totally useless) was to overcome the limits a factorial can have using any numeric types.
I simply took the idea from a tutorial that was using int variables. I could see, using printf() that the pointers being freed were not those pointing to 'mone', but I had not even thought about doing fact(mone, s); I vas concentrating on 'f' which was my target, and all the memory addresses were messed up.
As for not indenting the code; I had posted on another site where 4 leading blanks were needed for lines of code, so I used sed to produce such a file, but here it didn't work. I will read the FAQ and make sure to do things right in future.
Regards marian57

All times are GMT -5. The time now is 01:07 PM.