在递归期间,会创建一个堆栈,该堆栈包含什么,它包含值还是存储操作数的地址
void recursiveReverse(struct node** head_ref) { struct node* first; struct node* rest; /* empty list */ if (*head_ref == NULL) return; /* suppose first = {1, 2, 3}, rest = {2, 3} */ first = *head_ref; rest = first->next; /* List has only one node */ if (rest == NULL) return; /* reverse the rest list and put the first element at the end */ recursiveReverse(&rest); first->next->next = first; /* tricky step -- see the diagram */ first->next = NULL; /* fix the head pointer */ *head_ref = rest; }
在上面的代码中,当第一个指针继续改变时,其余指针保持最后一个节点的地址,即它正在从堆栈中获取值,而rest指针则没有。 所以首先我想知道递归堆栈,它的结构,它包含什么,它是如何工作的以及对上面代码的解释表示赞赏
我想知道递归堆栈,它的结构,它包含什么,它是如何工作的
递归函数与任何其他函数完全相似。 因此,对于递归函数的即时调用,它将像正常函数一样维护堆栈。 每次函数声明一个新变量时,它都会被压入堆栈。 然后每次函数退出时,该函数推送到堆栈的所有变量都被释放(也就是说,它们被删除)。 一旦释放了堆栈变量,该内存区域就可用于其他堆栈变量。
因此,当调用递归函数时,其所有变量都被压入堆栈,当它返回时,堆栈变量被释放。 请注意,自动局部变量被分配为单个块,并且堆栈指针的前进足够远以考虑其大小的总和。
简而言之,每次调用递归函数都会占用堆栈中的内存块。 请看下面C中的无限递归示例。
int foo() { int someVariable; return foo(); }
函数foo在被调用时继续调用自身,每次在堆栈上分配一块额外的空间,直到堆栈溢出导致分段错误。
有关其他信息,如果我们声明foo()
如下所示:
int foo() { double x[1024]; return foo(); }
然后每个递归调用, 1024 * sizeof(double)
的额外内存将在堆栈中分配给x
。 但是使用malloc()
将分配堆内存而不是堆栈 。
最后,每次调用递归函数 (包括返回值)时, 返回地址也会被压入堆栈。
如您所见,每个递归调用都会推送一个新的堆栈帧,然后如果递归无法达到基本情况,堆栈将很快耗尽并导致堆栈溢出。
参考: 基于堆栈的内存分配 , 堆栈溢出和内存堆栈与堆
以上就是c/c++开发分享C中的递归堆栈相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/549757.html