英文:
Why is the recursion depth in the algorithm so large?
问题
递归填充列表时，递归深度等于 (n^2 - n) / 2 而不是 n 的原因是因为每个元素都会触发一个新的递归调用，每个递归调用都会产生一个新的栈帧，导致递归深度呈二次增长。这是因为每个元素都会导致一个递归调用，而这个调用会继续调用下一个元素，以此类推，直到所有元素都添加到列表中。
因此，递归深度随着元素数量的增加呈二次增长，其数学表示为 (n^2 - n) / 2，而不是线性增长的 n。当元素数量超过3195时，递归深度超过了系统栈的限制，导致栈溢出错误。
英文:
Code for recursively filling in a unidirectional list:
#include <iostream>
#include <random>
using namespace std;
class Queue
{
private:
class Node;
public:
Queue()
{
size = 0;
head = nullptr;
}
Node* push_back(int data, Node* next)
{
static int depth; // recursion depth
if (next == nullptr)
{
next = new Node(data);
if (size == 0)
head = next;
size++;
return next;
}
depth++; // recursion depth
next->pNext = push_back(data, next->pNext);
return next;
}
Node* get_head() { return head; }
int get_size() { return size; }
private:
class Node
{
public:
Node* pNext;
int data;
Node(int data = int(), Node* pNext = nullptr)
{
this->data = data;
this->pNext = pNext;
}
};
int size;
Node* head;
};
Can you explain why the recursion depth when filling the list through a loop is equal to (n^2 - n) / 2, instead of n?
Because of this, a stack overflow occurs when the number of elements is greater than 3195.
答案1
得分: 0
这是因为在每次插入新值之前，没有将depth重置为零。
因此，当第二个值被推入链接列表时，depth首次从0增加到1。当第三个值插入链接列表时，depth再次从1增加到2，然后到3。以此类推。
您最终会计算出不仅是最后一个插入操作的递归深度，还包括所有插入操作的总和。
英文:
It's because nothing resets depth to zero, before each new value gets inserted.
So, when the 2nd value gets pushed into the linked list, depth gets incremented for the first time, from 0 to 1. When the 3rd value gets inserted into the linked list, depth then gets incremented from 1 to 2, then to 3. And so on.
You end up counting not just the recursion depth of the last insertion operation, but the sum total of all insertion operations.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论