c - 如何编写递归函数的迭代版本？

Question

我有一个函数，它接受一个大型长 double 组(65536 个元素)，并对每个元素执行一系列数学运算，最终得到一个修改后的数组，然后将其返回到 main。

问题是，它是递归的，并且有如此多的元素，程序和计算机最终崩溃，我只能假设这是由于堆栈溢出(!)。递归函数的代码如下:

long double *sift(long double *signal){
   int i, def;
   double maxsize, minsize;
   int *max,*min;
   long double *maxinterp, *mininterp,*upenv,*loenv,*protoimf;

   max = maxArray(signal, ARRAYSIZE); //build binary array indicating 
   min = minArray(signal, ARRAYSIZE); //maxima or minima at that index

   maxsize = count(max, ARRAYSIZE); //count total max/minima
   minsize = count(min, ARRAYSIZE);

   def = checkDefinition(signal, maxsize+minsize); 
   if(def>0) {          //checks if signal has equal number of zero
       return signal;   //crossings and extrema
   }

   maxinterp = gslMax(signal, maxsize, ARRAYSIZE); //gnu scientific lib
   mininterp = gslMin(signal, minsize, ARRAYSIZE); //cubic spline interp.

   upenv = envelope(maxinterp, max, min, maxsize, minsize); //envelopes of
   loenv = envelope(mininterp, min, max, minsize, maxsize); //signal

   protoimf = imf(signal, upenv, loenv); //find mean curve 
   protoimf = sift(protoimf);            //recursive call till definition
                                         //is satisfied
   if (def > 0) {
      return protoimf;
   }

   //free(min); free(upenv) etc. 

   return protoimf;
}

我尝试通过在 while 循环中调用 main 中的 sift() 来走迭代路线(在 ofc 中编辑递归)，并以 checkDefinition() 作为条件。但是，与递归相比，我没有得到相同的数组。我的辅助函数 countExtrema() 调用 max/minarray() 和 count() 并返回传入数组中的极值数。但是，该值与我执行递归时的值不同(这给出了正确的输出/行为)。

我认为这是因为我需要以某种方式存储局部变量？我在网上研究过，看来我可能需要一个堆栈？有人可以指导我如何在 c 中复制我的递归函数吗？

下面是我的 imf 函数的代码:

long double *imf(long double *hilbert, long double *upper, long double *lower){
   int i;
   long double *imf = malloc(sizeof(long double)*ARRAYSIZE);   //253
   for(i=0; i < ARRAYSIZE; i++){
      imf[i] = upper[i] + lower[i];
      imf[i] = imf[i] / 2.0000000000;
   }
   for(i = 0; i < ARRAYSIZE; i++){
      imf[i] = hilbert[i] - imf[i];
   }
   return imf;

}

这是 valgrind 的投诉:

15,728,400 bytes in 15 blocks are definitely lost in loss record 14 of 15
==10394==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10394==    by 0x401C68: imf (sift.c:253)
==10394==    by 0x402472: sift (sift.c:337)
==10394==    by 0x402626: main (sift.c:423)

还有很多对诸如envelope()这样的函数的提示 和 gslMin() 但它们都有相同的结构，我在其中分配一些内存并返回指向该内存的指针。问题是，如果我将 free 语句移至 sift() 中的 while 循环内，则会出现 seg 错误。我该如何修复这个内存泄漏？

Answer 1

1. 深度递归是一个坏兆头。您应该更彻底地检查您的算法。

2. 使用“类似堆栈”的数组来存储“递归上下文”，可以将任何递归算法转换为迭代算法。不用说，该阵列可以与可用 RAM 一样大。例如，参见快速排序迭代实现 - http://www.geeksforgeeks.org/iterative-quick-sort