Почему глубина рекурсии в алгоритме такая большая?
Код для рекурсивного заполнения однонаправленного списка:
#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^2 - n) / 2, а не n?
Из-за этого переполнение стека происходит, когда количество элементов превышает 3195.
Я понимаю, что рекурсия для этого не подходит, но не понимаю, зачем такая глубина. Моя задача состоит именно в рекурсивном способе заполнения списка
Потому что вы (предположительно) вызываете push_back несколько раз в своей программе, и каждый раз она увеличивает depth для каждого (рекурсивного или нет) вызова. Ваш depth ничего не говорит о глубине рекурсии. Он просто подсчитывает общее количество обращений к push_back в программе.
Если вы поддерживаете указатель на хвост, у вас может быть O (1) и не будет рекурсии для push_back.
Если вам нужна фактическая глубина рекурсии (а не сумма всех глубин рекурсии каждого предыдущего вызова), вам нужно каким-то образом сбросить depth (например, сбросить его до нуля, прежде чем вернуться к любому вызывающему объекту, кроме самого себя].
Мое правило: максимальная глубина рекурсии для рекурсивной функции должна быть O(log n). Такая реализация с глубиной O(n) вызывает проблемы: она быстро выйдет из строя с (не очень) большим n. И этот тип рекурсивной функции можно очень легко преобразовать в цикл, который легче понять, легче отлаживать, безопаснее и быстрее.
Ответы 1
Это потому, что ничто не сбрасывает depth на ноль, прежде чем будет вставлено каждое новое значение.
Итак, когда второе значение помещается в связанный список, depth увеличивается в первый раз, с 0 до 1. Когда 3-е значение вставляется в связанный список, depth затем увеличивается с 1 до 2, а затем до 3. И так далее.
В итоге вы подсчитываете не только глубину рекурсии последней операции вставки, но и общую сумму всех операций вставки.
"Объясните, почему глубина рекурсии при заполнении списка через цикл равна (n^2 - n)/2": Это не так. Вы просто неправильно используете статическую переменную
depth, которую вы никогда не обнуляете и не уменьшаете при возврате из рекурсивных вызовов. «переполнение стека происходит, когда количество элементов больше 3195»: это ожидается даже при линейной глубине рекурсии. Для этого не следует использовать рекурсивный алгоритм. Используйте итеративный. Также держите указатель на конец списка вокруг. Не повторяйте список несколько раз только для того, чтобы добавить что-то в конец.