递归填充单向链表时递归深度为何过大？为何为(n²-n)/2而非n？

递归填充链表的代码 #

#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;
};

递归深度为何是(n² - n)/2而非n？ #

问题核心在调用push_back的方式：如果是循环调用push_back(data, get_head())逐个添加n个元素，每次添加第k个元素（k从1到n）时：

• 第1个元素：直接创建节点，无需递归，递归深度贡献0
• 第2个元素：需要递归1次（遍历已有的1个节点找到尾节点）
• 第3个元素：需要递归2次（遍历已有的2个节点找到尾节点）
• ...
• 第n个元素：需要递归n-1次（遍历已有的n-1个节点找到尾节点）

总递归深度是1+2+...+(n-1)，这是首项为1、末项为n-1的等差数列求和，结果就是(n² - n)/2。

如果是一次性递归创建n个节点，或者每次添加时传递上一次的尾节点（而非从头节点开始遍历），递归深度才会是n或者常数级，但当前调用方式让递归次数随元素数量平方级增长，所以远大于n。

栈溢出的原因 #

每个递归调用都会占用栈空间存储栈帧（包括局部变量、返回地址等），平方级增长的递归次数会快速耗尽程序的默认栈空间。当元素数量超过3195时，总递归次数(3195²-3195)/2≈500万次，远超栈的承载能力，因此触发栈溢出。

内容的提问来源于stack exchange，提问作者MADA MADA