c - 如何避免在这个递归函数中使用malloc？

Question

我已经在 C 中实现了以下工作(正确的输出)递归 fft。我在递归函数中使用 malloc，这肯定会导致一些内存丢失，但我不知道如何避免它。我见过的大多数其他递归算法都会将相同的内存传递给递归调用(我认为它是就地调用的)，但我无法这样做。对于这种内存泄漏的直接解决方案会很棒，但相关 Material 的链接也将非常感激。

float complex *fft(float complex *in, int n, float complex w) {
  int i,j;
  if(fabs(crealf(w)-1.00f)<.0001f && fabs(cimagf(w)-0.00f)<0.0001f) {
    return in;
  }
  float complex *ine = malloc(n/2*sizeof(float complex));
  float complex *ino = malloc(n/2*sizeof(float complex));
  for(i=0,j=0;i<n;i++) {
    if(i%2==0){ 
      ine[j]=in[i];
    }
    else {
      ino[j++]=in[i];
    }
  }
  float complex *s = fft(ine,n/2,cpow(w,2));
  float complex *s1 = fft(ino,n/2,cpow(w,2));

  float complex *bad = malloc(n*sizeof(float complex));
  for (j=0; j<n/2; j++){
    bad[j] = s[j] + cpow(w,j) * s1[j];
    bad[j+n/2] = s[j] - cpow(w,j) * s1[j];
  }
  free(ine); free(ino);
  return bad;
}

返回一个指向函数内分配的内存的指针是否被认为是不好的做法，因为它将它留给调用者来释放该内存？

我尝试注册 Code Review，但“注册”按钮在我的旧浏览器上不起作用。

Answer 1

问题在于bad，因为递归函数的调用实例不知道递归调用是否返回传递的参数，或者新分配的指针bad。另外两个指针ine和ino没有问题，因为它们在分配它们的实例中总是free。

我当时正在编写一个解决方案，该解决方案管理分配的坏指针数组，这些指针可以在程序结束时释放，这时我想到了更好的解决方案。

添加新参数 int *newptr 通知调用者是否释放返回的指针，因为该指针不会向下传递回递归堆栈。

float complex *fft(float complex *in, int n, float complex w, int *newptr) {
  int i,j;
  int mem=0, mem1=0;                                    // added these flag vars
  if(fabs(crealf(w)-1.00f)<.0001f && fabs(cimagf(w)-0.00f)<0.0001f) {
    return in;                                          // no memory was allocated
  }
  float complex *ine = malloc(n/2*sizeof(float complex));
  float complex *ino = malloc(n/2*sizeof(float complex));
  for(i=0,j=0;i<n;i++) {
    if(i%2==0){ 
      ine[j]=in[i];
    }
    else {
      ino[j++]=in[i];
    }
  }
  // recursion starts here
  float complex *s = fft(ine,n/2,cpow(w,2), &mem);      // added extra arg
  float complex *s1 = fft(ino,n/2,cpow(w,2), &mem1);    // added extra arg

  float complex *bad = malloc(n*sizeof(float complex));
  *newptr = 1;                                          // flag memory allocated
  for (j=0; j<n/2; j++){
    bad[j] = s[j] + cpow(w,j) * s1[j];
    bad[j+n/2] = s[j] - cpow(w,j) * s1[j];
  }
  free(ine); free(ino);
  if (mem)
      free(s);                                          // free returned mem
  if (mem1)
      free(s1);                                         // free returned mem
  return bad;                                           // with newptr set
}