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

Question

我有一个函数，它接受大量的长双(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;
}

我试图以checkDefinition()为条件，在with循环中调用主循环中的sift() (用递归编辑了ofc)来执行迭代路由。但是，与递归相比，我没有得到相同的数组。我的助手函数countExtrema()调用max/minarray()和count()，并返回传入数组中的极值数。但是，这个值与我执行递归时的值不同(递归提供了正确的输出/行为)。

我想是因为我需要以某种方式存储局部变量？我在网上做过调查，看来我需要一堆东西？有人能指导我如何在c中复制递归函数吗？

下面是我的货币基金组织功能的代码：

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;

}

下面是瓦兰的抱怨：

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)

还有更多的关于函数的抱怨，比如信封()和gslMin()，但是它们都有相同的结构，其中我分配了一些内存并返回指向该内存的指针。问题是，如果我将空闲语句移到sift()中的while循环中，就会出现seg错误。我该如何修复这个内存泄漏？

Answer 1

您可以完全摆脱内存分配。下面是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 
    }
}

Answer 2

1. 深度复发是个不好的征兆。你应该更彻底地检查你的算法。
2. 可以将任何递归算法转换为迭代算法，使用“类堆栈”数组来存储“递归上下文”。不用说，这个数组可以和空闲RAM一样大。例如，请参见快速排序迭代实现- http://www.geeksforgeeks.org/iterative-quick-sort。

Answer 3

我注意到，在以下方面：

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

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

    return(sift(protoimf));
}