递归函数使用动态数组遇到的问题

在学习归并排序过程中，使用到了递归函数。而且例程在数组融合过程中，使用了动态数组。但是由于编译器不只支持长度变化的数组，所以我要将其改写为指针形式，从而进行自由的长度定义。

原例程：

T aux[r - l + 1];

修改后的程序语句：

int size = r - l + 1;
T *aux = new int[size];

虽然成功运行，但是一直有些疑问，递归过程释放空间的过程是怎样的呢，能否及时自动释放内存？递归层数过深是否会发生溢出？

通过查阅相关资料，知道了函数调用时通过栈（Stack）来实现的，栈的特性为先入后出，因此用栈来实现递归调用中的存储分配。每当调用一个函数，栈就会加一层栈帧，函数返回就减一层栈帧。递归的下层函数没有返回，是不会释放当前资源的，要不然递归无法继续执行。但是栈的资源是有限，当递归深度达到一定程度后，就有可能发生溢出。解决方法可以利用循环函数或者使用栈加while循环来代替递归函数，不过这不是本文重点，不再具体叙述。

在解决上述动态数组问题时，也曾考虑使用vector进行替换：

int size = r - l + 1;
vector<T> aux;
aux.reserve(size);

但是执行时一直报错vector越界，后来经过语法检查发现了问题：reserve是容器预留空间，但在空间内并没有真正创建了元素对象，所以没有添加新的元素前，是不能有效地访问这些内存空间的。所以访问的时候就会出现越界现象，导致程序崩溃。

Vec.reserve(r-l+1 );     // 新元素还没有构造, 仅仅申请内存空间
                         // 此时不能用[]下标访问元素
for (int i = 0; i < r-l+1; i++ )
{ 
     Vec.push_back( i ); //新元素此时才构造
}

终于将坑填好了，将此段程序加入reserve下面就可以正常访问与修改了。不过此方法有点小缺陷在于当使用了for循环，导致原排序算法时间复杂度会变化。

 

原文链接:https://www.cnblogs.com/uestczdc/p/12577418.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有