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

Question

我有一个函数，它接受大量长双精度数组（65536 个元素）并对每个元素执行一堆数学运算，最终得到一个修改后的数组，然后 returned 到 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;
}

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

我想是因为我需要以某种方式存储局部变量？我在网上研究过，看来我可能需要一个堆栈？有人可以指导我如何在 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() 但它们都具有相同的结构，我在其中分配了一些内存和 return 指向该内存的指针。问题是，如果我将我的自由语句移动到 sift() 的 while 循环内，我会遇到段错误。我该如何解决此内存泄漏问题？

Answer 1

深度递归是个坏兆头。你应该更彻底地检查你的算法。
可以将任何递归算法转化为迭代算法，使用"stack-like"数组存储"recursion context"。不用说，该数组可以和空闲 RAM 一样大。例如，参见快速排序迭代实现 - http://www.geeksforgeeks.org/iterative-quick-sort

Answer 2

我注意到：

if (def > 0) {
  return protoimf;
}
//free memory

def 永远不会 > 0，因为之前已经检查过一些行。然后，如果您可以将 "free memory" 部分移动到 protoimf = sift(protoimf); 之前，您将剩下尾递归，适当的编译器可以对其进行优化以避免实际执行递归。函数的最后一行变为：

    return(sift(protoimf));
}

Answer 3

您可以完全摆脱内存分配。这是 imf 函数的简化版本：

void imf(long double *hilbert, long double *upper, long double *lower) {
    for (int i = 0; i < ARRAYSIZE; i++) {
        hilbert[i] -= (upper[i] + lower[i]) / 2.0;
}

sift也可以简化。它将迭代地就地修改 signal 数组。

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

    for (;;) {
        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

        imf(signal, upenv, loenv); //find mean curve 
    }
}

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

How do I write an iterative version of my recursive function?

c

arrays

recursion

interpolation

signal-processing